oj.uz

Submission #965133

# Submission time Handle Problem Language Result Execution time Memory
965133 2024-04-18T07:32:05 Z PieArmy Regions (IOI09_regions) C++17
100 / 100
 2063 ms 78416 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;
    };
    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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 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 7 ms 8792 KB Output is correct
6 Correct 13 ms 8792 KB Output is correct
7 Correct 17 ms 8792 KB Output is correct
8 Correct 20 ms 8792 KB Output is correct
9 Correct 30 ms 9304 KB Output is correct
10 Correct 45 ms 9048 KB Output is correct
11 Correct 76 ms 9304 KB Output is correct
12 Correct 89 ms 9720 KB Output is correct
13 Correct 101 ms 9264 KB Output is correct
14 Correct 143 ms 11808 KB Output is correct
15 Correct 168 ms 18156 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 16892 KB Output is correct
2 Correct 768 ms 15128 KB Output is correct
3 Correct 1267 ms 19600 KB Output is correct
4 Correct 161 ms 9900 KB Output is correct
5 Correct 227 ms 11856 KB Output is correct
6 Correct 477 ms 31556 KB Output is correct
7 Correct 683 ms 35056 KB Output is correct
8 Correct 956 ms 43360 KB Output is correct
9 Correct 1239 ms 16092 KB Output is correct
10 Correct 1925 ms 76528 KB Output is correct
11 Correct 2063 ms 14808 KB Output is correct
12 Correct 806 ms 46236 KB Output is correct
13 Correct 1066 ms 46652 KB Output is correct
14 Correct 1514 ms 52228 KB Output is correct
15 Correct 1803 ms 67028 KB Output is correct
16 Correct 1799 ms 78416 KB Output is correct
17 Correct 1845 ms 68324 KB Output is correct