Submission #965133

#	Time	Username	Problem	Language	Result	Execution time	Memory
965133		PieArmy	Regions (IOI09_regions)	C++17	100 / 100	2063 ms	78416 KiB

regions

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

int n,sq,R,Q;
int renk[200001],fazlapos[25001],bas[200001],son[200001],say[25001];
int pre[25001][447],pre2[447][25001];
vector<int>child[200001],var[25001];

int cal(int a,int b){
    if(say[b]==0||say[a]==0){
        return 0;
    }
    if(say[b]>sq){
        return pre[a][fazlapos[b]];
    }
    if(say[a]>sq){
        return pre2[fazlapos[a]][b];
    }
    int sta[say[a]];
    int tavan=-1;
    int apos=0;
    int ans=0;
    for(int i=0;i<say[b];i++){
        while(tavan!=-1&&son[sta[tavan]]<bas[var[b][i]]){
            tavan--;
        }
        while(apos<say[a]&&bas[var[a][apos]]<=bas[var[b][i]]){
            if(son[var[a][apos]]>=bas[var[b][i]]){
                tavan++;
                sta[tavan]=var[a][apos];
            }
            apos++;
        }
        ans+=tavan+1;
    }
    return ans;
}

int main(){
    cin>>n>>R>>Q;
    sq=sqrt(n);
    cin>>renk[1];
    int time=0;
    say[renk[1]]++;
    for(int &x:fazlapos)
        x=-1;
    for(int i=2;i<=n;i++){
        int par;cin>>par;
        child[par].pb(i);
        cin>>renk[i];
        if(say[renk[i]]==sq){
            fazlapos[renk[i]]=time;
            time++;
        }
        say[renk[i]]++;
    }
    function<int(int,int)>f=[&](int pos,int tur)->int{
        int res=0;
        for(int x:child[pos]){
            res+=f(x,tur);
        }
        if(renk[pos]==tur)return res+1;
        pre[renk[pos]][fazlapos[tur]]+=res;
        return res;
    };
    for(int i=1;i<=R;i++){
        if(fazlapos[i]==-1)continue;
        f(1,i);
        queue<pair<int,int>>q;
        q.push({1,0});
        while(q.size()){
            int pos=q.front().first,sum=q.front().second;
            q.pop();
            if(renk[pos]!=i)pre2[fazlapos[i]][renk[pos]]+=sum;
            else sum++;
            for(int x:child[pos]){
                q.push({x,sum});
            }
        }
    }
    time=1;
    function<void(int)>turla=[&](int pos)->void{
        if(say[renk[pos]]<=sq){
            bas[pos]=time;
            var[renk[pos]].pb(pos);
        }
        time++;
        for(int x:child[pos]){
            turla(x);
        }
        child[pos].clear();
        son[pos]=time-1;
    };
    turla(1);
    while(Q--){
        int a,b;cin>>a>>b;
        cout<<cal(a,b)<<endl;
    }
}

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