Submission #1019493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019493		boyliguanhan	Regions (IOI09_regions)	C++17	100 / 100	7458 ms	68100 KiB

regions

#include<bits/stdc++.h>
#include<bits/extc++.h>
#pragma GCC optimize(3)
using namespace __gnu_pbds;
using namespace std;
#define N 200100
#define SZ 410
int CC,in[N],out[N],id[N],prc[SZ][SZ],hv[SZ],CC2,reg[N],ANS,T[N];
vector<int>hav[N],adj[N];
gp_hash_table<int,int> sup[SZ],sub[SZ],sup2[SZ],sub2[SZ];
void upd(gp_hash_table<int,int>&mp,int x,int v){
    while(x<N)mp[x]+=v,x+=x&-x;
}
void query(gp_hash_table<int,int>&mp,int x,int v){
    while(x)ANS+=mp[x]*v,x-=x&-x;
}
void upd2(int x,int v){
    while(x<N) T[x]+=v,x+=x&-x;
}
void query2(int x,int v){
    while(x) ANS+=T[x]*v,x-=x&-x;
}
void dfs(int n){
    if(id[reg[n]])for(int i=1;i<=CC2;i++)
        prc[i][id[reg[n]]]+=hv[i];
    hv[id[reg[n]]]++; in[n]=++CC;
    for(auto i:adj[n])dfs(i);
    hv[id[reg[n]]]--; out[n]=CC;
    if(id[reg[n]])
        upd(sup[id[reg[n]]],in[n],1),
        upd(sup[id[reg[n]]],out[n]+1,-1),
        upd(sub[id[reg[n]]],in[n],1);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,q,r;
    cin>>n>>r>>q;
    cin>>reg[1];
    for(int i=2;i<=n;i++){
        int p;cin>>p>>reg[i];
        adj[p].push_back(i);
    }
    for(int i=1;i<=n;i++)
        hav[reg[i]].push_back(i);
    for(int i=1;i<=r;i++)
        if(hav[i].size()>=500)
            id[i]=++CC2;
    dfs(1);
    for(int i=1;i<=CC2;i++)
        sub2[i]=sub[i],sup2[i]=sup[i];
    while(q--){
        int a,b;
        cin>>a>>b;
        ANS=0;
        if(id[a]&&id[b])
            ANS=prc[id[a]][id[b]];
        else if(id[a]||id[b])
            if(hav[a].size()>hav[b].size())
                for(auto i:hav[b])
                    query(sup[id[a]],in[i],1);
            else for(auto i:hav[a])
                query(sub[id[b]],in[i]-1,-1),
                query(sub[id[b]],out[i],1);
        else {
            for(auto i:hav[a])
                upd2(in[i],1),
                upd2(out[i]+1,-1);
            for(auto i:hav[b])
                query2(in[i],1);
            for(auto i:hav[a])
                upd2(in[i],-1),
                upd2(out[i]+1,1);
        }
        cout<<ANS<<endl;
        if(q%500==0)for(int i=1;i<=CC2;i++)
            sub[i]=sub2[i],sup[i]=sup2[i];
    }
}

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