Submission #381037

#	Time	Username	Problem	Language	Result	Execution time	Memory
381037		parsabahrami	Tropical Garden (IOI11_garden)	C++17	100 / 100	2785 ms	33976 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
 
const int N = 3e5 + 10;
int n, m, q, cnt[2], mn[N], M[2][N], C[2][N], out[N], dp[2][N]; vector<int> adj[N];

int cycDFS(int v, int t) {
    if (C[t][v]) return 0;
    if (M[t][v]) { 
        C[t][v] = 1;
        return 1;
    }
    M[t][v] = 1;
    int u = out[v];
    int f = cycDFS(u, t);
    if (C[t][v]) return 0;
    return C[t][v] = f;
}

void BFS(int st) {
    int *pd = dp[st >= n];
    fill(pd, pd + N, 2e9);
    pd[st] = 0; queue<int> Q; Q.push(st);
    while (SZ(Q)) {
        int v = Q.front(); Q.pop();
        for (int u : adj[v]) 
            if (pd[u] > pd[v] + 1) 
                pd[u] = pd[v] + 1, Q.push(u);
    }
}

inline int check(int p, int v, int x) {
    if (dp[p >= n][v] > x) return 0;
    int tmp = (!C[p >= n][p] ? 2e9 : cnt[p >= n]);
    int f = !((x - dp[p >= n][v]) % tmp);
    return f;
}

void count_routes(int _n, int _m, int P, int R[][2], int _q, int G[]) {
    n = _n, m = _m, q = _q;
    fill(mn, mn + N, 2e9);
    for (int i = 0; i < m; i++) {
        adj[R[i][0]].push_back(i), mn[R[i][0]] = min(mn[R[i][0]], i);
        adj[R[i][1]].push_back(i), mn[R[i][1]] = min(mn[R[i][1]], i);
    }
    for (int i = 0; i < n * 2; i++) {
        if (i >= n) {
            int v = R[mn[i - n]][0] ^ (i - n) ^ R[mn[i - n]][1];
            if (mn[i - n] == mn[v]) out[i] = v;
            else out[i] = v + n;
        } else {
            int sec = -1;
            for (int id : adj[i]) 
                if (id != mn[i]) { sec = id; break; }
            if (!~sec) sec = mn[i];
            int v = R[sec][0] ^ i ^ R[sec][1];
            if (sec == mn[v]) out[i] = v;
            else out[i] = v + n;
        }
    }
    memset(C, 0, sizeof C);
    cycDFS(P, 0); cycDFS(P + n, 1);
    for (int i = 0; i < 2 * n; i++)
        cnt[0] += C[0][i], cnt[1] += C[1][i];
    for (int i = 0; i < n; i++) 
        adj[i] = {};
    for (int i = 0; i < 2 * n; i++) 
        adj[out[i]].push_back(i);
    BFS(P), BFS(P + n);
    for (int _ = 0; _ < q; _++) {
        int x = G[_], f = 0;
        for (int i = n; i < 2 * n; i++) {
            f += (check(P, i, x) || check(P + n, i, x));
        }
        answer(f);
    }
}

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