Submission #1174356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174356		AlgorithmWarrior	Regions (IOI09_regions)	C++20	100 / 100	1977 ms	55056 KiB

regions

#include <bits/stdc++.h>

using namespace std;

int const SQRT=316;
int const MAX=2e5+5;
int n,loc,q;
int region[MAX];
int tata[MAX];
vector<int>tree[MAX];
vector<int>ans[MAX][2];
int freq[MAX];
int tin[MAX],tout[MAX];
vector<int>nodes[MAX];

void read(){
    cin>>n>>loc>>q>>region[1];
    ++freq[region[1]];
    int i;
    for(i=2;i<=n;++i){
        cin>>tata[i]>>region[i];
        tree[tata[i]].push_back(i);
        ++freq[region[i]];
    }
}

int dfs_init(int nod,int cnt,int reg){
    int sum=0;
    for(auto fiu : tree[nod])
        sum+=dfs_init(fiu,cnt+(reg==region[nod]),reg);
    if(region[nod]!=reg){
        ans[reg][0][region[nod]]+=cnt;
        ans[reg][1][region[nod]]+=sum;
    }
    return sum+(reg==region[nod]);
}

void dfs_euler(int nod){
    static int time=0;
    nodes[region[nod]].push_back(nod);
    tin[nod]=++time;
    for(auto fiu : tree[nod])
        dfs_euler(fiu);
    tout[nod]=++time;
}

void precalc(){
    int i;
    for(i=1;i<=loc;++i)
        if(freq[i]>SQRT){
            ans[i][0].resize(loc+5,0);
            ans[i][1].resize(loc+5,0);
            dfs_init(1,0,i);
        }
    dfs_euler(1);
}

stack<int>stv;

int add(int nod,int tip){
    while(!stv.empty() && tout[stv.top()]<tin[nod])
        stv.pop();
    if(tip==1)
        stv.push(nod);
    return stv.size();
}

void process_queries(){
    while(q--){
        int u,v;
        cin>>u>>v;
        if(freq[u]>SQRT)
            cout<<ans[u][0][v]<<endl;
        else
            if(freq[v]>SQRT)
                cout<<ans[v][1][u]<<endl;
            else{
                int i=0,j=0;
                int answer=0;
                while(i<freq[u] && j<freq[v]){
                    if(tin[nodes[u][i]]<tin[nodes[v][j]]){
                        add(nodes[u][i],1);
                        ++i;
                    }
                    else{
                        answer+=add(nodes[v][j],2);
                        ++j;
                    }
                }
                while(i<freq[u]){
                    add(nodes[u][i],1);
                    ++i;
                }
                while(j<freq[v]){
                    answer+=add(nodes[v][j],2);
                    ++j;
                }
                while(!stv.empty())
                    stv.pop();
                cout<<answer<<endl;
            }
    }
}

int main()
{
    read();
    precalc();
    process_queries();
    return 0;
}

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