oj.uz

Submission #965125

# Submission time Handle Problem Language Result Execution time Memory
965125 2024-04-18T07:24:47 Z PieArmy Regions (IOI09_regions) C++17
100 / 100
 2082 ms 78384 KB 
#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;
    };
    function<void(int,int,int)>f2=[&](int pos,int tur,int sum)->void{
        if(renk[pos]!=tur)pre2[fazlapos[tur]][renk[pos]]+=sum;
        else sum++;
        for(int x:child[pos]){
            f2(x,tur,sum);
        }
    };
    for(int i=1;i<=R;i++){
        if(fazlapos[i]==-1)continue;
        f(1,i);
        f2(1,i,0);
    }
    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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 5 ms 8788 KB Output is correct
5 Correct 6 ms 8788 KB Output is correct
6 Correct 15 ms 8792 KB Output is correct
7 Correct 18 ms 8792 KB Output is correct
8 Correct 22 ms 8792 KB Output is correct
9 Correct 35 ms 9304 KB Output is correct
10 Correct 47 ms 9304 KB Output is correct
11 Correct 71 ms 9304 KB Output is correct
12 Correct 86 ms 9644 KB Output is correct
13 Correct 106 ms 9376 KB Output is correct
14 Correct 136 ms 11976 KB Output is correct
15 Correct 182 ms 18156 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 16936 KB Output is correct
2 Correct 826 ms 15084 KB Output is correct
3 Correct 1242 ms 19424 KB Output is correct
4 Correct 175 ms 10000 KB Output is correct
5 Correct 233 ms 11856 KB Output is correct
6 Correct 543 ms 31556 KB Output is correct
7 Correct 740 ms 36156 KB Output is correct
8 Correct 942 ms 49940 KB Output is correct
9 Correct 1189 ms 15872 KB Output is correct
10 Correct 2082 ms 76680 KB Output is correct
11 Correct 2063 ms 15016 KB Output is correct
12 Correct 832 ms 47372 KB Output is correct
13 Correct 1076 ms 48336 KB Output is correct
14 Correct 1681 ms 55408 KB Output is correct
15 Correct 1742 ms 67176 KB Output is correct
16 Correct 1751 ms 78384 KB Output is correct
17 Correct 1850 ms 71416 KB Output is correct