oj.uz

Submission #964915

# Submission time Handle Problem Language Result Execution time Memory
964915 2024-04-17T17:26:26 Z PieArmy Regions (IOI09_regions) C++17
95 / 100
 2054 ms 131072 KB 
typedef long long ll;
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

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

ll 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]];
    ll tavan=-1;
    int apos=0;
    ll 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[sirali[a][apos]]<=bas[var[b][i]]){
            if(son[sirali[a][apos]]>=bas[var[b][i]]){
                tavan++;
                sta[tavan]=sirali[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<ll(int,int)>f=[&](int pos,int tur)->ll{
        ll 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,ll)>f2=[&](int pos,int tur,ll 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);
            sirali[renk[pos]].pb(pos);
        }
        time++;
        for(int x:child[pos]){
            turla(x);
        }
        son[pos]=time-1;
    };
    turla(1);
    for(int i=1;i<=R;i++){
        if(say[i]>sq)continue;
        sort(sirali[i].begin(),sirali[i].end(),[&](const int &x,const int &y){
            if(bas[x]==bas[y]){
                return son[x]<son[y];
            }
            return bas[x]<bas[y];
        });
    }
    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 3 ms 8792 KB Output is correct
5 Correct 7 ms 8792 KB Output is correct
6 Correct 12 ms 8792 KB Output is correct
7 Correct 17 ms 8792 KB Output is correct
8 Correct 18 ms 8792 KB Output is correct
9 Correct 33 ms 9504 KB Output is correct
10 Correct 53 ms 9048 KB Output is correct
11 Correct 75 ms 9344 KB Output is correct
12 Correct 86 ms 9924 KB Output is correct
13 Correct 99 ms 9528 KB Output is correct
14 Correct 142 ms 11964 KB Output is correct
15 Correct 165 ms 16380 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 18836 KB Output is correct
2 Correct 776 ms 15156 KB Output is correct
3 Correct 1291 ms 19552 KB Output is correct
4 Correct 174 ms 10068 KB Output is correct
5 Correct 240 ms 11848 KB Output is correct
6 Correct 522 ms 49980 KB Output is correct
7 Correct 751 ms 59044 KB Output is correct
8 Correct 997 ms 76912 KB Output is correct
9 Correct 1318 ms 17000 KB Output is correct
10 Runtime error 884 ms 131072 KB Execution killed with signal 9
11 Correct 2054 ms 16164 KB Output is correct
12 Correct 856 ms 74988 KB Output is correct
13 Correct 1136 ms 76016 KB Output is correct
14 Correct 1678 ms 93184 KB Output is correct
15 Correct 1765 ms 112904 KB Output is correct
16 Correct 1809 ms 124028 KB Output is correct
17 Correct 1875 ms 109080 KB Output is correct