Submission #835116

#	Time	Username	Problem	Language	Result	Execution time	Memory
835116		Denkata	Regions (IOI09_regions)	C++17	100 / 100	4173 ms	27420 KiB

regions

#include<bits/stdc++.h>
using namespace std;
const int crit = 450;
const int maxn = 2e5+3;
const int maxr = 25003;
int i,j,p,q,n,m,R,Q,k,tin[maxn],tout[maxn],br,cnt[crit+3][maxr],hora[maxn],type[maxn],cur,d,nom[maxn];
vector <int> v[maxn];
vector <int> vid[maxr];
vector <int> kraishta[maxr];
void dfs(int u)
{
    tin[u]=++br;
    for(auto i:v[u])
        dfs(i);
    tout[u]=++br;
    kraishta[type[u]].push_back(tin[u]);
}
void dfs2(int u)
{
    cnt[nom[i]][type[u]]+=cur;
    if(type[u]==i)
        cur++;
    for(auto j:v[u])
        dfs2(j);
    if(type[u]==i)
        cur--;
}
int calc()
{
    int ans = 0;
    for(auto i:vid[p])
    {
        int l = lower_bound(kraishta[q].begin(),kraishta[q].end(),tin[i]) - kraishta[q].begin();
        int r = lower_bound(kraishta[q].begin(),kraishta[q].end(),tout[i]+1) - kraishta[q].begin() - 1;
        //cout<<i<<" "<<tin[i]<<" "<<tout[i]<<" "<<l<<" "<<r<<" "<<kraishta[q][l]<<" "<<kraishta[q][r]<<endl;
        if(l>r)continue;  
        l = max(0,l);l = min(l,(int)kraishta[q].size()-1);
        r = max(0,r);r = min(r,(int)kraishta[q].size()-1);    
        ans+=r-l+1;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>R>>Q;
    cin>>p;
    hora[p]++;type[1] = p;vid[p].push_back(1);
    for(i=2;i<=n;i++)
    {
        cin>>p>>q;
        hora[q]++;
        type[i] = q;
        vid[q].push_back(i);
        v[p].push_back(i);
    }
    dfs(1);
    for(i=1;i<=R;i++)
    {
        if(hora[i]>=crit)
        {
           // cur = 0;
            nom[i]=++d;
            dfs2(1);
        }
    }
    for(i=1;i<=n;i++)
        sort(kraishta[i].begin(),kraishta[i].end());
    while(Q--)
    {
        cin>>p>>q;
        if(hora[p]>crit)
            cout<<cnt[nom[p]][q]<<endl;
        else
            cout<<calc()<<endl;
    }
    return 0;
}

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