Submission #1063227

#TimeUsernameProblemLanguageResultExecution timeMemory
1063227BoasTropical Garden (IOI11_garden)C++17
69 / 100
5076 ms48988 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 void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { vvi adj(N); loop(M, i) { adj[R[i][0]].pb(R[i][1]); adj[R[i][1]].pb(R[i][0]); } vvi p(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]; } } auto nthParent = [&](int i, int n) -> int { loop(30, x) { if ((1 << x) & n) { i = p[x][i]; } } return i; }; for (int i = 0; i < Q; i++) { int K = G[i]; int cnt = 0; loop(N, start) { 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...