Submission #49787

#TimeUsernameProblemLanguageResultExecution timeMemory
49787gs13105Tropical Garden (IOI11_garden)C++17
100 / 100
70 ms13792 KiB
#include <cstdio> #include <cstdlib> #include <cstring> #include <cassert> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <list> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <tuple> #include <iterator> using namespace std; void answer(int x); const int MAXN = 150000; const int MAXN2 = MAXN * 2; int arr[MAXN2 + 10]; int dis[2][MAXN2 + 10]; bool chk[2][MAXN2 + 10]; void f(int x, int p) { //assert(!chk[p % 2][x]); chk[p % 2][x] = 1; if(arr[x] == p) { //assert(!dis[p % 2][x]); dis[p % 2][x] = 1; return; } if(!chk[p % 2][arr[x]]) f(arr[x], p); //assert(!dis[p % 2][x]); if(dis[p % 2][arr[x]]) dis[p % 2][x] = dis[p % 2][arr[x]] + 1; } int mem1[MAXN + 10]; int mem2[MAXN + 10]; int sum[2][MAXN2 + 10]; void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { memset(mem1, -1, sizeof mem1); memset(mem2, -1, sizeof mem2); memset(arr, -1, sizeof arr); for(int i = 0; i < M; i++) { int x = R[i][0]; int y = R[i][1]; if(mem1[x] == -1) mem1[x] = y; else if(mem2[x] == -1) mem2[x] = y; if(mem1[y] == -1) mem1[y] = x; else if(mem2[y] == -1) mem2[y] = x; } for(int i = 0; i < N; i++) { //assert(mem1[i] != -1); if(mem1[mem1[i]] == i && mem2[mem1[i]] != -1) arr[2 * i] = 2 * mem1[i] + 1; else arr[2 * i] = 2 * mem1[i]; if(mem2[i] != -1) { if(mem1[mem2[i]] == i && mem2[mem2[i]] != -1) arr[2 * i + 1] = 2 * mem2[i] + 1; else arr[2 * i + 1] = 2 * mem2[i]; } } for(int r = 0; r < 2; r++) for(int i = 0; i < 2 * N; i++) if(!chk[r][i] && arr[i] != -1) f(i, 2 * P + r); for(int r = 0; r < 2; r++) for(int i = 0; i < N; i++) if(dis[r][2 * i]) /*assert(dis[r][2 * i] <= 2 * N), */sum[r][dis[r][2 * i]]++; for(int r = 0; r < 2; r++) { int c = dis[r][2 * P + r]; if(!c) continue; for(int i = 1; i <= 2 * N; i++) if(i - c >= 1) sum[r][i] += sum[r][i - c]; } //assert(dis[0][2 * P] == 0 || dis[1][2 * P + 1] == 0 || dis[0][2 * P] == dis[1][2 * P + 1]); //int c = max(dis[0][2 * P], dis[1][2 * P + 1]); int c1 = dis[0][2 * P]; int c2 = dis[1][2 * P + 1]; if(c1 == 0) c1 = c2; if(c2 == 0) c2 = c1; for(int i = 0; i < Q; i++) { int r = 0; { int t = G[i]; if(t > 2 * N && c1) t -= ((t - 2 * N + c1 - 1) / c1) * c1; if(t <= 2 * N) r += sum[0][t]; } { int t = G[i]; if(t > 2 * N && c2) t -= ((t - 2 * N + c2 - 1) / c2) * c2; if(t <= 2 * N) r += sum[1][t]; } answer(r); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...