Submission #1244242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244242		whtth	Regions (IOI09_regions)	C++20	85 / 100	8057 ms	31396 KiB

regions

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int n, m, r, k, ans=0, sz[200010], x, y, z, st[200010], en[200010], timer=0, qg[200010];
vector<int> ke[200010];
vector<int> f[25001];
void dfs(int u, int t){
    st[u]=++timer;
    f[qg[u]].push_back(u);
    sz[u]=1;
    for(int v : ke[u]){
        if(v!=t){
            dfs(v, u);
            sz[u]+=sz[v];
        }
    }
    en[u]=timer;
}
bool cmp(int a, int b){
    return st[a]<st[b];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    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 : f[x]){
            int L=-1, R=-1;
            int l=0, r=f[y].size()-1, mid;
            while(l<=r){
                mid=(l+r)/2;
                if(en[u]>=st[f[y][mid]]){
                    R=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }
            l=0, r=f[y].size()-1;
            while(l<=r){
                mid=(l+r)/2;
                if(st[u]<=st[f[y][mid]]){
                    L=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            if(R==-1 || L==-1)continue;
            ans+=(R-L+1);
        }
        cout<<ans<<endl;
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 70 / 85