Submission #1202689

#TimeUsernameProblemLanguageResultExecution timeMemory
1202689aykhnTropical Garden (IOI11_garden)C++20
0 / 100
7 ms14656 KiB
#include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> using namespace std; const int MXN = 3e5 + 5; vector<int> adj[MXN]; vector<array<int, 2>> g[MXN]; int incyc[MXN], par[MXN]; int used[MXN]; int sz[2] = {0, 0}; void dfs(int a, int f) { used[a] = 1; for (int &v : adj[a]) { if (used[v] == 2) continue; if (used[v] == 0) { par[v] = a; dfs(v, f); } else { int e = a; while (1) { sz[f]++; incyc[e] = 1; if (e == v) break; e = par[e]; } } } used[a] = 2; } void add_edge(int u, int v) { adj[v].push_back(u); } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { for (int i = 0; i < M; i++) { auto [u, v] = R[i]; g[u].push_back({i, v}); g[v].push_back({i, u}); } for (int i = 0; i < N; i++) { if (g[i].empty()) continue; sort(g[i].begin(), g[i].end()); int A = g[i][0][1]; if (g[A][0][1] == i) A = A * 2 + 1; else A = A * 2; add_edge(2 * i, A); if (g[i].size() == 1) { add_edge(2 * i + 1, A); continue; } A = g[i][1][1]; if (g[A][0][1] == i) A = A * 2 + 1; else A = A * 2; add_edge(2 * i + 1, A); } dfs(P * 2, 0); dfs(P * 2 + 1, 1); int d[2][N * 2], seen[2][N * 2]; for (int i = 0; i < 2; i++) { fill(d[i], d[i] + N * 2, -1); fill(seen[i], seen[i] + N * 2, 0); queue<int> q; d[i][P * 2 + i] = 0, q.push(P * 2 + i); while (!q.empty()) { int a = q.front(); seen[i][a] |= incyc[a]; q.pop(); for (int &v : adj[a]) { if (d[i][v] == -1) continue; d[i][v] = d[i][a] + 1; seen[i][v] = seen[i][a]; q.push(v); } } } for (int i = 0; i < Q; i++) { int x = G[i], res = 0; for (int j = 0; j < N; j++) { int ok = 0; for (int l = 0; l < 2; l++) { if (d[l][2 * j] == -1 || d[l][2 * j] > x) continue; if (seen[l][2 * j]) ok |= (x - d[l][2 * j]) % sz[l] == 0; else ok |= d[l][2 * j] == x; } res += ok; } answer(res); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...