제출 #1063365

#제출 시각아이디문제언어결과실행 시간메모리
1063365Boas열대 식물원 (Tropical Garden) (IOI11_garden)C++17
100 / 100
2702 ms75116 KiB
#include "gardenlib.h" #include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; #define loop(x, i) for (int i = 0; i < x; i++) #define pb push_back // position within the cycle, -1 if not in the cycle vi pos; // distance to the cycle vi dis; // index of last parent *not* in cycle vi entryPoint; vi component, cycleLengths; vvi revrs; // euler tour stuff vi in, out; vvi p; int getNthParent(int x, int k) { loop(30, i) { if ((1 << i) & k) x = p[i][x]; } return x; } int getDis(int a, int b) { if (component[a] != component[b]) return -1; int res = 0; if (pos[a] == -1) { if (pos[a] == pos[b]) { if (entryPoint[a] == entryPoint[b] && dis[a] >= dis[b]) { int k = dis[a] - dis[b]; if (getNthParent(a, k) == b) return k; return -1; } return -1; } res += dis[a]; a = p[0][entryPoint[a]]; } if (pos[b] == -1) { return -1; } if (component[a] != component[b]) throw; int cycleLength = cycleLengths[component[a]]; res += (pos[b] - pos[a] + cycleLength) % cycleLength; return res; } void cycleNumbering(int i, int nr) { if (pos[i] != -1) { cycleLengths.pb(nr); return; } pos[i] = nr; cycleNumbering(p[0][i], nr + 1); } void revDFS(int i, int c) { component[i] = c; for (int j : revrs[i]) { if (component[j] == -1) { revDFS(j, c); } } } void DFS(int i, int c) { if (component[i] != -1) { cycleNumbering(i, 0); return; } revDFS(i, c); DFS(p[0][i], c); } int counter = 0; void euler(int i) { in[i] = counter; counter++; for (int j : revrs[i]) { euler(j); } out[i] = counter; counter++; } ii getEntryPoint(int i) { if (entryPoint[i] != -1) return {entryPoint[i], dis[i]}; if (pos[p[0][i]] != -1) { dis[i] = 1; entryPoint[i] = i; counter = 0; euler(i); return {i, 1}; } auto [j, d] = getEntryPoint(p[0][i]); entryPoint[i] = j; dis[i] = d + 1; return {j, d + 1}; } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { in = out = vi(2 * N); vvi adj(N); loop(M, i) { adj[R[i][0]].pb(R[i][1]); adj[R[i][1]].pb(R[i][0]); } p = vvi(30, vi(2 * N)); loop(N, i) { int j = adj[i][0]; if (adj[j][0] == i) j += N; p[0][i] = j; if (adj[i].size() == 1) { p[0][i + N] = j; } else { j = adj[i][1]; if (adj[j][0] == i) j += N; p[0][i + N] = j; } } for (int x = 1; x < 30; x++) { loop(2 * N, i) { int half = p[x - 1][i]; p[x][i] = p[x - 1][half]; } } pos = dis = entryPoint = component = vi(2 * N, -1); revrs = vvi(2 * N); loop(2 * N, i) { revrs[p[0][i]].pb(i); } int c = 0; loop(2 * N, i) { if (component[i] == -1) { DFS(i, c); c++; } } loop(2 * N, i) { if (pos[i] == -1 && entryPoint[i] == -1) { getEntryPoint(i); } } for (int i = 0; i < Q; i++) { int K = G[i]; int cnt = 0; loop(N, start) { auto reachesGoal = [&](int goal) -> bool { if (component[start] != component[goal]) return 0; if (pos[goal] >= 0) { int l = cycleLengths[component[goal]]; if (pos[start] >= 0) { return ((pos[goal] - pos[start] + l) % l) == (K % l); } else { int d = dis[start]; if (d > K) return 0; int cur = p[0][entryPoint[start]]; return ((pos[goal] - pos[cur] + l) % l) == ((K - d) % l); } } else if (entryPoint[start] == entryPoint[goal]) { if (dis[start] == dis[goal] + K) { // check with euler tour // if (getNthParent(start, K) == goal) if (in[start] >= in[goal] && in[start] <= out[goal]) return 1; // not always... } } return 0; }; if (reachesGoal(P) || reachesGoal(P + N)) cnt++; // if (nthParent(start, K) % N == P) cnt++; } answer(cnt); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...