oj.uz

Submission #964913

# Submission time Handle Problem Language Result Execution time Memory
964913 2024-04-17T17:19:47 Z PieArmy Regions (IOI09_regions) C++17
95 / 100
 2132 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][450],pre2[450][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 2 ms 8792 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 6 ms 9044 KB Output is correct
6 Correct 13 ms 9044 KB Output is correct
7 Correct 20 ms 8792 KB Output is correct
8 Correct 24 ms 9048 KB Output is correct
9 Correct 34 ms 9304 KB Output is correct
10 Correct 57 ms 9304 KB Output is correct
11 Correct 68 ms 9560 KB Output is correct
12 Correct 88 ms 9992 KB Output is correct
13 Correct 115 ms 9668 KB Output is correct
14 Correct 148 ms 14372 KB Output is correct
15 Correct 173 ms 18776 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 21640 KB Output is correct
2 Correct 774 ms 17880 KB Output is correct
3 Correct 1271 ms 22256 KB Output is correct
4 Correct 187 ms 10272 KB Output is correct
5 Correct 229 ms 12224 KB Output is correct
6 Correct 524 ms 50576 KB Output is correct
7 Correct 761 ms 59820 KB Output is correct
8 Correct 962 ms 77556 KB Output is correct
9 Correct 1329 ms 18072 KB Output is correct
10 Runtime error 917 ms 131072 KB Execution killed with signal 9
11 Correct 2132 ms 17472 KB Output is correct
12 Correct 839 ms 78148 KB Output is correct
13 Correct 1093 ms 78952 KB Output is correct
14 Correct 1590 ms 96408 KB Output is correct
15 Correct 1758 ms 114188 KB Output is correct
16 Correct 1776 ms 125412 KB Output is correct
17 Correct 1910 ms 112312 KB Output is correct