제출 #1324583

#제출 시각아이디문제언어결과실행 시간메모리
1324583JungPSRegions (IOI09_regions)C++20
19 / 100
8077 ms23040 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];

void dfs(int x){
    tour.push_back(x);
    inout[x].first=timer;
    ++timer;
    for(auto i:vec[x]){
        if(inout[i].first) continue;
        dfs(i);
    }
    tour.push_back(-x);
    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);
    while(q--){
        int r1,r2; cin >> r1 >> r2;
        int ans=0;
        for(auto i:home[r1]){
            for(int j=inout[i].first;j<=inout[i].second;++j){
                if(tour[j]>0 && h[tour[j]]==r2) ++ans;
            }
        }
        cout << ans << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...