oj.uz

Submission #965118

# Submission time Handle Problem Language Result Execution time Memory
965118 2024-04-18T07:16:39 Z PieArmy Regions (IOI09_regions) C++17
100 / 100
 2079 ms 78456 KB 
typedef long long ll;
#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<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);
        }
        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 3 ms 8792 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 13 ms 8796 KB Output is correct
7 Correct 21 ms 8792 KB Output is correct
8 Correct 23 ms 8792 KB Output is correct
9 Correct 30 ms 9304 KB Output is correct
10 Correct 48 ms 9076 KB Output is correct
11 Correct 77 ms 9304 KB Output is correct
12 Correct 81 ms 9816 KB Output is correct
13 Correct 102 ms 9276 KB Output is correct
14 Correct 140 ms 11780 KB Output is correct
15 Correct 173 ms 18288 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 16768 KB Output is correct
2 Correct 698 ms 15112 KB Output is correct
3 Correct 1242 ms 19456 KB Output is correct
4 Correct 173 ms 9856 KB Output is correct
5 Correct 227 ms 11836 KB Output is correct
6 Correct 512 ms 31560 KB Output is correct
7 Correct 716 ms 36152 KB Output is correct
8 Correct 1004 ms 49952 KB Output is correct
9 Correct 1245 ms 16104 KB Output is correct
10 Correct 2079 ms 76356 KB Output is correct
11 Correct 2011 ms 14812 KB Output is correct
12 Correct 814 ms 47372 KB Output is correct
13 Correct 1043 ms 48468 KB Output is correct
14 Correct 1517 ms 52856 KB Output is correct
15 Correct 1759 ms 67056 KB Output is correct
16 Correct 1738 ms 78456 KB Output is correct
17 Correct 1853 ms 70344 KB Output is correct