oj.uz

Submission #965121

# Submission time Handle Problem Language Result Execution time Memory
965121 2024-04-18T07:19:03 Z PieArmy Regions (IOI09_regions) C++17
100 / 100
 2063 ms 78376 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 2 ms 8792 KB Output is correct
4 Correct 4 ms 8792 KB Output is correct
5 Correct 6 ms 8792 KB Output is correct
6 Correct 12 ms 8792 KB Output is correct
7 Correct 15 ms 8792 KB Output is correct
8 Correct 23 ms 8888 KB Output is correct
9 Correct 29 ms 9304 KB Output is correct
10 Correct 54 ms 9300 KB Output is correct
11 Correct 70 ms 9304 KB Output is correct
12 Correct 88 ms 9700 KB Output is correct
13 Correct 103 ms 9212 KB Output is correct
14 Correct 137 ms 11996 KB Output is correct
15 Correct 162 ms 18268 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 16768 KB Output is correct
2 Correct 734 ms 15084 KB Output is correct
3 Correct 1219 ms 19532 KB Output is correct
4 Correct 172 ms 9760 KB Output is correct
5 Correct 232 ms 11716 KB Output is correct
6 Correct 505 ms 31316 KB Output is correct
7 Correct 730 ms 36144 KB Output is correct
8 Correct 913 ms 49948 KB Output is correct
9 Correct 1230 ms 16264 KB Output is correct
10 Correct 2063 ms 76496 KB Output is correct
11 Correct 2035 ms 14804 KB Output is correct
12 Correct 841 ms 47468 KB Output is correct
13 Correct 1071 ms 48640 KB Output is correct
14 Correct 1479 ms 55400 KB Output is correct
15 Correct 1643 ms 67096 KB Output is correct
16 Correct 1710 ms 78376 KB Output is correct
17 Correct 1921 ms 68584 KB Output is correct