Submission #1221228

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

garden

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

int n, m, k;
vector<int> lead, cycSize;
vector<bool> targ, cyc;
vector<vector<int>> best, g, specDis;

void find_cycles() {
    vector<int> deg(n, 0);
    cyc.assign(n, true);
    for (int i = 0; i < n; i++) deg[lead[i]]++;
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        cyc[curr] = false;
        deg[lead[curr]]--;
        if (deg[lead[curr]] == 0) q.push(lead[curr]);
    }
}

void get_cyc_dp() {
    cycSize.assign(n, 0);
    specDis.assign(n, vector<int>(2, -2));
    for (int i = 0; i < n; i++) {
        if (!cyc[i] || cycSize[i] != 0) continue;
        int curr = lead[i];
        int tot = 1;
        while (curr != i) {
            if (curr == 2 * k) {
                specDis[i][0] = tot;
            }
            if (curr == 2 * k ^ 1) {
                specDis[i][1] = tot;
            }
            tot++;
            curr = lead[curr];
        }
        if (curr == 2 * k) specDis[i][0] = 0;
        if (curr == 2 * k ^ 1) specDis[i][1] = 0;
        cycSize[i] = tot;
        int prev = i;
        curr = lead[i];
        while (curr != i) {
            specDis[curr][0] = max(-2, specDis[prev][0] - 1);
            specDis[curr][1] = max(-2, specDis[prev][1] - 1);
            if (specDis[curr][0] == -1) specDis[curr][0] = cycSize[i] - 1;
            if (specDis[curr][1] == -1) specDis[curr][1] = cycSize[i] - 1;
            cycSize[curr] = cycSize[i];
            prev = curr;
            curr = lead[curr];
        }
    }
}

void get_rest_dp() {
    vector<vector<int>> revG(n);
    vector<int> deg(n, 0);
    for (int i = 0; i < n; i++) {
        if (cyc[i] || cyc[lead[i]]) continue;
        revG[lead[i]].push_back(i);
        deg[i]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (cyc[i]) continue;
        if (deg[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        if (curr == 2 * k) {
            specDis[curr][0] = 0;
        }
        else {
            if (specDis[lead[curr]][0] == -2) continue;
            specDis[curr][0] = specDis[lead[curr]][0] + 1;
        }
        if (curr == 2 * k ^ 1) {
            specDis[curr][1] = 0;
        }
        else {
            if (specDis[lead[curr]][1] == -2) continue;
            specDis[curr][1] = specDis[lead[curr]][1] + 1;
        }
        cycSize[curr] = cycSize[lead[curr]];
        for (auto nxt: revG[curr]) {
            deg[nxt]--;
            if (deg[nxt] == 0) q.push(nxt);
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    n = N;
    m = M;
    k = P;
    lead.assign(2*n, -1);
    best.assign(n, vector<int>(2, -1));
    for (int i = 0; i < m; i++) {
        int u = R[i][0];
        int v = R[i][1];
        if (best[u][0] == -1) best[u][0] = i;
        else if (best[u][1] == -1) best[u][1] = i;
        if (best[v][0] == -1) best[v][0] = i;
        else if (best[v][1] == -1) best[v][1] = i;
    }
    for (int u = 0; u < n; u++) {
        if (best[u][1] == -1) best[u][1] = best[u][0];
        int v = u ^ R[best[u][0]][0] ^ R[best[u][0]][1];
        if (best[u][0] != best[v][0]) {
            lead[2 * u] = 2 * v;
        }
        else lead[2 * u] = 2 * v ^ 1;
        v = u ^ R[best[u][1]][0] ^ R[best[u][1]][1];
        if (best[u][1] != best[v][0]) {
            lead[2 * u ^ 1] = 2 * v;
        }
        else lead[2 * u ^ 1] = 2 * v ^ 1;
    }
    n *= 2;
    targ.assign(n, false);
    targ[2 * k] = targ[2 * k ^ 1] = true;
    cyc.assign(n, false);
    find_cycles();
    get_cyc_dp();
    get_rest_dp();
    for (int i = 0; i < Q; i++) {
        int dis = G[i];
        int tot = 0;
        for (int j = 0; j < n; j+=2) {
            bool f = false;
            if (specDis[j][0] <= dis && specDis[j][0] != -2) {
                if ((dis - specDis[j][0]) % cycSize[j] == 0) f = true;
            }
            if (specDis[j][1] <= dis && specDis[j][1] != -2) {
                if ((dis - specDis[j][1]) % cycSize[j] == 0) f = true;
            }
            tot += f;
        }
        answer(tot);
    }
}

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