Submission #1125139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125139		BestCrazyNoob	Tropical Garden (IOI11_garden)	C++20	0 / 100	1 ms	576 KiB

garden

#include <vector>
#include <utility>
#include <cassert>
#include "garden.h"
#include "gardenlib.h"

using namespace std;
using pii = pair<int, int>;
constexpr int INF = 1e9;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    vector<int> to(2*N, -1);
    for (int i = 0; i < M; i++) {
        const bool first0 = to[R[i][0]] == -1;
        const bool first1 = to[R[i][1]] == -1;
        if (to[R[i][0]] == -1) {
            to[R[i][0]] = R[i][1] + (first1 ? N : 0);
        } else if (to[R[i][0] + N] == -1) {
            to[R[i][0] + N] = R[i][1] + (first1 ? N : 0);
        }
        if (to[R[i][1]] == -1) {
            to[R[i][1]] = R[i][0] + (first0 ? N : 0);
        } else if (to[R[i][1] + N] == -1) {
            to[R[i][1] + N] = R[i][0] + (first0 ? N : 0);
        }
    }

    for (int i = 0; i < N; i++) {
        if (to[i+N] == -1) {
            to[i+N] = to[i];
        }
    }

    vector<vector<int>> from(2*N);

    for (int i = 0; i < 2*N; i++) {
        if (to[i] != -1) from[to[i]].push_back(i);
    }

    // or -1
    auto cycle_length = [&](int x) -> int {
        int len = 0, curr = x;
        while (len < 2*N+1 && to[curr] != -1) {
            len++;
            curr = to[curr];
            if (curr == x) return len;
        }
        return -1;
    };

    auto dfs = [&](auto &&dfs, int curr, vector<int> &dist) -> void {
        assert(dist[curr] != -1);
        for (int c: from[curr]) {
            if (dist[c] != -1) continue;
            dist[c] = dist[curr]+1;
            dfs(dfs, c, dist);
        }
    };

    int len = cycle_length(P), len2 = cycle_length(P+N);
    if (len == -1) len = INF;
    if (len2 == -1) len2 = INF;
    vector<int> dist(2*N, -1), dist2(2*N, -1);
    dist[P] = 0; dist2[P+N] = 0;
    dfs(dfs, P, dist);
    dfs(dfs, P+N, dist2);

    vector<int> byD(2*N, 0), byD2(2*N, 0);

    for (int i = 0; i < N; i++) {
        if (dist[i] != -1) {
            byD[dist[i] % len]++;
        }
        if (dist2[i] != -1) {
            byD2[dist2[i] % len2]++;
        }
    }

    for(int q = 0; q < Q; q++) {
        int ans = 0;
        if (G[q] % len < 2*N) ans += byD[G[q] % len];
        if (G[q] % len2 < 2*N) ans += byD2[G[q] % len2];
        answer(ans);
    }
}

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