Submission #1324584

#TimeUsernameProblemLanguageResultExecution timeMemory
1324584JungPSRegions (IOI09_regions)C++20
40 / 100
8071 ms25136 KiB
#include<bits/stdc++.h>
using namespace std;

int h[200007];
vector<int> home[25007];
vector<int> vec[200007];
vector<int> tour;
int timer=1;
pair<int,int> inout[100007];

vector<int> touridx[25007];
void dfs(int x){
    tour.push_back(h[x]);
    inout[x].first=timer;
    ++timer;
    for(auto i:vec[x]){
        if(inout[i].first) continue;
        dfs(i);
    }
    tour.push_back(0);
    inout[x].second=timer;
    ++timer;
}
signed main(){
    int n,r,q; cin >> n >> r >> q;
    cin >> h[1];
    for(int i=2;i<=n;++i){
        int s; cin >> s >> h[i];
        vec[i].push_back(s);
        vec[s].push_back(i); 
    }
    for(int i=1;i<=n;++i){
        home[h[i]].push_back(i);
    }
    tour.push_back(0);
    dfs(1);
    for(int i=0;i<tour.size();++i) touridx[tour[i]].push_back(i);
    while(q--){
        int r1,r2; cin >> r1 >> r2;
        int ans=0;
        for(auto i:home[r1]){
            ans+=upper_bound(touridx[r2].begin(),touridx[r2].end(),inout[i].second)-lower_bound(touridx[r2].begin(),touridx[r2].end(),inout[i].first);
        }
        cout << ans << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...