Submission #1210340

#TimeUsernameProblemLanguageResultExecution timeMemory
1210340spampotsRegions (IOI09_regions)C++20
82 / 100
8055 ms28432 KiB
#include<bits/stdc++.h> using namespace std; int main(){ int N, R, Q; cin >> N >> R >> Q; vector<vector<int>> adj(N+1); vector<int> region(N+1); vector<vector<int>> comp(R+1); cin >> region[1]; for(int i = 2; i <= N; ++i){ int x; cin >> x; adj[x].push_back(i); cin >> region[i]; } int timer(0); vector<int> in(N), out(N), euler(N); function<void(int)> dfs = [&](int node){ in[node] = timer++; euler[in[node]] = node; comp[region[node]].push_back(in[node]); for(int x : adj[node]) dfs(x); out[node] = timer; }; dfs(1); for(int i = 0; i < Q; ++i){ int r1, r2; cin >> r1 >> r2; int ans(0); for(int x : comp[r1]) ans += lower_bound(comp[r2].begin(), comp[r2].end(), out[euler[x]]) - lower_bound(comp[r2].begin(), comp[r2].end(), x); cout << ans << endl; fflush(stdout); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...