Submission #50968

#	Time	Username	Problem	Language	Result	Execution time	Memory
50968		aquablitz11	Tropical Garden (IOI11_garden)	C++14	100 / 100	2785 ms	45892 KiB

garden

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

const int N = 150010;
const int INF = 1e9;

vector<int> mn[N], G[2*N];
int nxt[2*N], deg[2*N], h[2*N][3], ph[2*N][3];
bool comp[2*N][3];

void expand(int u, int c, int s, int d=0, int p=-INF)
{
    if (comp[u][c])
        return;
    if (deg[u] == 0 && (u == 2*s || u == 2*s+1)) {
        //assert(p < 0);
        p = 0;
    }
    h[u][c] = d, ph[u][c] = p;
    comp[u][c] = true;
    for (auto v : G[u])
        expand(v, c, s, d+1, p+1);
}

void count_routes(int n, int m, int p, int R[][2], int q, int K[])
{
    // find min and second-min
    for (int i = 0; i < m; ++i) {
        int u = R[i][0], v = R[i][1];
        if (mn[u].size() < 2)
            mn[u].push_back(v);
        if (mn[v].size() < 2)
            mn[v].push_back(u);
    }

    // completely fill second-min
    for (int i = 0; i < n; ++i) {
        if (mn[i].size() == 0) continue;
        if (mn[i].size() == 1) mn[i].push_back(mn[i].back());
    }

    // find nxt of each node
    for (int i = 0; i < n; ++i) {
        nxt[2*i] = nxt[2*i+1] = -1;
        if (mn[i].size() == 0) continue;
        // normal node
        int j = mn[i][0];
        if (mn[j][0] != i) nxt[2*i] = 2*j;
        else nxt[2*i] = 2*j+1;
        // walked node
        j = mn[i][1];
        if (mn[j][0] != i) nxt[2*i+1] = 2*j;
        else nxt[2*i+1] = 2*j+1;
    }

    // find degree and make reversed graph: G
    for (int u = 0; u < 2*n; ++u) {
        if (nxt[u] == -1) continue;
        ++deg[nxt[u]];
        G[nxt[u]].push_back(u);
    }

    // find cycle
    queue<int> Q;
    for (int u = 0; u < 2*n; ++u) {
        if (nxt[u] != -1 && deg[u] == 0)
            Q.push(u);
    }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        if (--deg[nxt[u]] == 0)
            Q.push(nxt[u]);
    }
    //for (int u = 0; u < 2*n; ++u)
        //assert(deg[u] == 0 || deg[u] == 1);

    // expand
    expand(2*p, 1, p);
    expand(2*p+1, 2, p);

    // find cycle size for 2*p and 2*p+1 (just in case they're different)
    int c1 = 0, u = 2*p;
    if (deg[u] == 1) {
        do {
            ++c1;
            u = nxt[u];
        } while (u != 2*p);
    }

    int c2 = 0;
    u = 2*p+1;
    if (deg[u] == 1) {
        do {
            ++c2;
            u = nxt[u];
        } while (u != 2*p+1);
    }

    //assert(c1 == 0 || c2 == 0 || c1 == c2);

    // answer each query
    for (int i = 0; i < q; ++i) {
        int k = K[i], cnt = 0;
        for (int u = 0; u < 2*n; u += 2) {
            if (nxt[u] == -1) continue;
            bool ans = false;
            if (comp[u][1]) {
                ans |= ph[u][1] == k;
                ans |= c1 > 0 && k-h[u][1] >= 0 && (k-h[u][1])%c1 == 0;
            }
            if (comp[u][2]) {
                ans |= ph[u][2] == k;
                ans |= c2 > 0 && k-h[u][2] >= 0 && (k-h[u][2])%c2 == 0;
            }
            if (ans) ++cnt;
        }
        answer(cnt);
    }

}

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