Submission #118208

#TimeUsernameProblemLanguageResultExecution timeMemory
118208nvmdavaTropical Garden (IOI11_garden)C++17
100 / 100
2979 ms9188 KiB
#include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> using namespace std; int n, p; int to[300005]; int best[150005][2]; bool proc[300005][2]; int cyc[2]; int t[300005][2]; void dfs1(int v){ if(proc[v][0]) return; proc[v][0] = 1; if(v == p) return; dfs1(to[v]); t[v][0] = t[to[v]][0] + 1; } void dfs0(int v){ if(proc[v][1]) return; proc[v][1] = 1; if(v == p + n) return; dfs0(to[v]); t[v][1] = t[to[v]][1] + 1; } void count_routes(int n, int m, int p, int r[][2], int q, int g[]){ memset(best, -1, sizeof best); memset(t, 0x3f, sizeof t); for(int i = 0; i < m; i++){ int v = r[i][0], u = r[i][1]; if(best[v][0] == -1) best[v][0] = u; else if(best[v][1] == -1) best[v][1] = u; if(best[u][0] == -1) best[u][0] = v; else if(best[u][1] == -1) best[u][1] = v; } ::n = n; ::p = p; for(int i = 0; i < n; i++) if(best[i][1] == -1) best[i][1] = best[i][0]; for(int i = 0; i < n; i++){ to[i] = best[i][0] + n * (best[best[i][0]][0] == i); to[i + n] = best[i][1] + n * (best[best[i][1]][0] == i); } t[p][0] = 0; t[p + n][1] = 0; for(int i = 0; i < n * 2; i++){ dfs1(i); dfs0(i); } cyc[0] = 1 + t[to[p]][0]; cyc[1] = 1 + t[to[n + p]][1]; for(int j = 0; j < q; j++){ int res = 0; for(int i = 0; i < n; i++){ if((t[i][0] < 0x3f3f3f3f && (g[j] - t[i][0]) % cyc[0] == 0 && g[j] >= t[i][0]) || (t[i][1] < 0x3f3f3f3f && g[j] >= t[i][1] && (g[j] - t[i][1]) % cyc[1] == 0)) res++; } answer(res); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...