Submission #1244260

#TimeUsernameProblemLanguageResultExecution timeMemory
1244260whtthRegions (IOI09_regions)C++20
0 / 100
62 ms29472 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; int n, m, r, k, ans=0, x, y, z, st[200010], en[200010], timer=0, qg[200010]; vector<int> ke[200010]; vector<int> f[25001]; vector<int> g[25001]; void dfs(int u, int t){ st[u]=++timer; f[qg[u]].push_back(st[u]); g[qg[u]].push_back(u); for(int v : ke[u]){ if(v!=t){ dfs(v, u); } } en[u]=timer; } bool cmp(int a, int b){ return st[a]<st[b]; } int main(){ ios::sync_with_stdio(0);cin.tie(nullptr); cin>>n>>r>>m; for(int i=1;i<=n;i++){ int x, y; if(i!=1){ cin>>x; ke[x].push_back(i); } cin>>qg[i]; } dfs(1, 0); for(int i=1;i<=m;i++){ int x, y, ans=0; cin>>x>>y; for(int u : g[x]){ auto itL = lower_bound(f[y].begin(), f[y].end(), st[u]); auto itR = upper_bound(f[y].begin(), f[y].end(), en[u]); ans += (itR - itL); } cout<<ans<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...