Submission #964916

#	Time	Username	Problem	Language	Result	Execution time	Memory
964916		PieArmy	Regions (IOI09_regions)	C++17	95 / 100	2033 ms	131072 KiB

regions

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];
ll pre[25001][447],pre2[447][25001];
vector<int>child[200001],var[25001],sirali[25001];

ll cal(int a,int b){
    if(sirali[b].size()==0||sirali[a].size()==0){
        return 0;
    }
    if(sirali[b].size()>sq){
        return pre[a][fazlapos[b]];
    }
    if(sirali[a].size()>sq){
        return pre2[fazlapos[a]][b];
    }
    int sta[sirali[a].size()];
    ll tavan=-1;
    int apos=0;
    ll ans=0;
    for(int i=0;i<sirali[b].size();i++){
        while(tavan!=-1&&son[sta[tavan]]<bas[var[b][i]]){
            tavan--;
        }
        while(apos<sirali[a].size()&&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;
    sirali[renk[1]].pb(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(sirali[renk[i]].size()==sq){
            fazlapos[renk[i]]=time;
            time++;
        }
        sirali[renk[i]].pb(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(sirali[renk[pos]].size()<=sq){
            bas[pos]=time;
            var[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(sirali[i].size()>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;
    }
}

Compilation message (stderr)

regions.cpp: In function 'll cal(int, int)':
regions.cpp:15:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     if(sirali[b].size()>sq){
      |        ~~~~~~~~~~~~~~~~^~~
regions.cpp:18:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     if(sirali[a].size()>sq){
      |        ~~~~~~~~~~~~~~~~^~~
regions.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<sirali[b].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~
regions.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         while(apos<sirali[a].size()&&bas[sirali[a][apos]]<=bas[var[b][i]]){
      |               ~~~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:53:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         if(sirali[renk[i]].size()==sq){
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~
regions.cpp: In lambda function:
regions.cpp:82:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |         if(sirali[renk[pos]].size()<=sq){
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'int main()':
regions.cpp:94:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         if(sirali[i].size()>sq)continue;
      |            ~~~~~~~~~~~~~~~~^~~

• Subtask 1: 15 / 15
• Subtask 2: 80 / 85