제출 #433107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433107		someone	Tropical Garden (IOI11_garden)	C++14	0 / 100	1 ms	588 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int i, t;
};

const int N = 3e3 + 42, Q = 2e3 + 10, INF = 2e9;

bool b[N][2];
Node nex[N][2];
vector<int> adj[N];
vector<Node> pre[N][2];
int n, m, fin, q, step[Q], occ[N][2], arc[N], cycle[2], dist[N][2][2];

void BFS(int k) {
    queue<Node> q;
    q.push({fin, k});
    dist[fin][k][k] = 0;
    while(!q.empty()) {
        Node act = q.front();
        q.pop();
        for(Node next : pre[act.i][act.t]) {
            if(dist[next.i][next.t][k] == INF) {
                dist[next.i][next.t][k] = dist[act.i][act.t][k] + 1;
                q.push(next);
            }
        }
    }
}

void count_routes(int N_, int M_, int P_, int R[][2], int Q_, int G[]) {
    n = N_, m = M_, fin = P_, q = Q_;
    for(int i = 0; i < m; i++)
        arc[i] = R[i][0] + R[i][1];
    for(int i = 0; i < m; i++) {
        if(adj[R[i][0]].size() < 2) {
            adj[R[i][0]].push_back(i);
        }
        if(adj[R[i][1]].size() < 2) {
            adj[R[i][1]].push_back(i);
        }
    }
    for(int i = 0; i < n; i++)
        if(adj[i].size() == 1)
            adj[i].push_back(adj[i][0]);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < 2; j++) {
            int s = arc[adj[i][j]] - i;
            if(adj[i][j] == adj[s][0]) {
                nex[i][j] = {s, 1};
                pre[s][1].push_back({i, j});
            } else {
                nex[i][j] = {s, 0};
                pre[s][0].push_back({i, j});
            }
        }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                dist[i][j][k] = INF;
    int i = fin, j = 0, nb = 0;
    cycle[0] = cycle[1] = -1;
    do {
        nb++;
        b[i][j] = true;
        Node next = nex[i][j];
        i = next.i;
        j = next.t;
    } while(!b[i][j]);
    if(i == fin && j == 0) {
        cycle[0] = nb;
    }
    for(int i = 0; i < n; i++)
        b[i][0] = b[i][1] = false;
    i = fin, j = 1, nb = 0;
    do {
        nb++;
        b[i][j] = true;
        Node next = nex[i][j];
        i = next.i;
        j = next.t;
    } while(!b[i][j]);
    if(i == fin && j == 1) {
        cycle[1] = nb;
    }
    BFS(0);
    BFS(1);
    for(int k = 0; k < 2; k++)
        if(cycle[k] != -1) {
            for(int i = 0; i < n; i++)
                if(dist[i][0][k] != INF)
                    occ[dist[i][0][k] % cycle[k]][k]++;
        } else {
            for(int i = 0; i < n; i++)
                if(dist[i][0][k] != INF)
                    occ[dist[i][0][k]][k]++;
        }
    for(int i = 0; i < q; i++) {
        int ans = 0;
        if(cycle[0] != -1) {
            ans += occ[G[i] % cycle[0]][0];
        } else {
            if(G[i] < N) {
                ans += occ[G[i]][0];
            }
        }
        if(cycle[1] != -1) {
            ans += occ[G[i] % cycle[1]][1];
        } else {
            if(G[i] < N) {
                ans += occ[G[i]][1];
            }
        }
        answer(ans);
    }
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31