Submission #1019482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019482		vjudge1	Regions (IOI09_regions)	C++17	25 / 100	8098 ms	127024 KiB

regions

#include<bits/stdc++.h>
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;
vector<int>hav[N],adj[N];
map<int,int> sup[SZ],sub[SZ];
void upd(map<int,int>&mp,int x,int v){
    while(x<N) mp[x]+=v,x+=x&-x;
}
void query(map<int,int>&mp,int x,int v){
    while(x) ANS+=mp[x]*v,x-=x&-x;
}
void dfs(int n){
    if(id[reg[n]])for(int i=1;i<SZ;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);
    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 {
            map<int,int>mp;
            for(auto i:hav[a])
                upd(mp,in[i],1),
                upd(mp,out[i]+1,-1);
            for(auto i:hav[b])
                query(mp,in[i],1);
        }
        cout<<ANS<<endl;
    }
}

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