Submission #1019483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019483		vjudge1	Regions (IOI09_regions)	C++17	32 / 100	6154 ms	131072 KiB

regions

#include<bits/stdc++.h>
using namespace std;
#define N 200100
#define SZ 410
#define R 25010
int CC,in[N],out[N],id[R],prc[SZ][SZ],hv[SZ],CC2,reg[N],ANS;
vector<int>hav[N],adj[N];
map<int,int> sup[R],sub[R];
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;
    upd(sup[reg[n]],in[n],1);
    upd(sup[reg[n]],out[n]+1,-1);
    upd(sub[reg[n]],in[n],1);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,q;
    cin>>n>>q>>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(hav[a].size()>hav[b].size())
            for(auto i:hav[b])
                query(sup[a],in[i],1);
        else for(auto i:hav[a])
            query(sub[b],in[i]-1,-1),
            query(sub[b],out[i],1);
        cout<<ANS<<endl;
    }
}

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