Submission #298240

#TimeUsernameProblemLanguageResultExecution timeMemory
298240tatyamTropical Garden (IOI11_garden)C++17
69 / 100
5094 ms41976 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int INF = 0x3fffffff; template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; } void answer(int x); void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){ vector g(N, array{pii{INF, -1}, pii{INF, -1}}); // 各頂点から最も美しい 2 つの辺を持つ for(int i = 0; i < M; i++){ auto [a, b] = R[i]; if(chmin(g[a][1], {i, b}) && g[a][1] < g[a][0]) swap(g[a][0], g[a][1]); if(chmin(g[b][1], {i, a}) && g[b][1] < g[b][0]) swap(g[b][0], g[b][1]); } for(auto& [e1, e2] : g) if(e2.first == INF) e2 = e1; vector next(30, vector<int>(N * 2)); // ダブリング for(int i = 0; i < N; i++){ { const auto [a, b] = g[i][0]; if(a != INF) next[0][i * 2] = b * 2 + (a == g[b][0].first); } { const auto [a, b] = g[i][1]; if(a != INF) next[0][i * 2 + 1] = b * 2 + (a == g[b][0].first); } } for(int i = 0; i < 29; i++) for(int j = 0; j < N * 2; j++) next[i + 1][j] = next[i][next[i][j]]; for(int i = 0; i < Q; i++){ const int K = G[i]; int ans = 0; for(int i = 0; i < N; i++){ int at = i * 2; for(int i = 0; K >> i; i++) if(K >> i & 1) at = next[i][at]; ans += at / 2 == P; } answer(ans); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...