# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1105180 | 2024-10-25T16:10:16 Z | anarch_y | Tropical Garden (IOI11_garden) | C++17 | 0 ms | 0 KB |
#include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) begin(x), end(x) #define sz(x) (int)x.size() #define pb push_back int main(){ int n, m; cin >> n >> m; vector<pair<int, int>> vec[n]; int mn[n] = {}; for(int i=1; i<=m; i++){ int a, b; cin >> a >> b; vec[a].pb({b, i}); vec[b].pb({a, i}); if(mn[a] == 0) mn[a] = i; if(mn[b] == 0) mn[b] = i; } int to[2*n] = {}; for(int a=0; a<n; a++){ auto [b, i] = vec[a][0]; if(mn[b] == i) to[a] = n+b; else to[a] = b; if(sz(vec[a]) >= 2){ auto [c, j] = vec[a][1]; if(mn[c] == j) to[n+a] = n+c; else to[n+a] = c; } else{ if(mn[b] == i) to[n+a] = n+b; else to[n+a] = b; } } int succ[2*n][20] = {}; for(int a=0; a<2*n; a++){ succ[a][0] = to[a]; } for(int i=1; i<20; i++){ for(int a=0; a<2*n; a++){ succ[a][i] = succ[succ[a][i-1]][i-1]; } } int p; cin >> p; int q; cin >> q; int qry[q] = {}; for(int i=0; i<q; i++) cin >> qry[i]; for(int i=0; i<q; i++){ int k = qry[i]; int ans = 0; for(int a=0; a<n; a++){ int x = a; for(int i=0; i<20; i++){ if(k & (1<<i)) x = succ[x][i]; } if(x == p or x == n+p) ans++; } answer(ans); } }