제출 #593360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593360		Bench0310	Regions (IOI09_regions)	C++17	100 / 100	2648 ms	33612 KiB

regions

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=200005;
const int R=25005;
const int S=105;
const int BIG=N/S;
vector<int> v[N];
int h[N];
vector<int> region[R];
int all[R];
int tcnt=0;
int tin[N];
int tout[N];
vector<int> down[R];
vector<array<int,2>> up[R];
int bigres[BIG][BIG];
vector<int> big;
int bigid[R];
int cnt[R];
int bigcnt=0;

void add_up(int r,int t,int d)
{
    auto [pt,ps]=up[r].back();
    if(pt==t) up[r].back()[1]+=d;
    else up[r].push_back({t,ps+d});
}

void dfs(int a)
{
    tin[a]=tcnt++;
    down[h[a]].push_back(tin[a]);
    add_up(h[a],tin[a],1);
    if(bigid[h[a]]!=-1)
    {
        for(int r:big) bigres[bigid[r]][bigid[h[a]]]+=cnt[r];
    }
    cnt[h[a]]++;
    for(int to:v[a]) dfs(to);
    tout[a]=tcnt-1;
    add_up(h[a],tout[a]+1,-1);
    cnt[h[a]]--;
}

int qdown(int x,int l,int r)
{
    return upper_bound(down[x].begin(),down[x].end(),r)-lower_bound(down[x].begin(),down[x].end(),l);
}

int qup(int x,int t)
{
    auto it=lower_bound(up[x].begin(),up[x].end(),array<int,2>{t+1,0});
    return (*prev(it))[1];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,r,q;
    cin >> n >> r >> q;
    for(int i=1;i<=r;i++) up[i].push_back({-1,0});
    for(int i=1;i<=n;i++)
    {
        if(i>=2)
        {
            int p;
            cin >> p;
            v[p].push_back(i);
        }
        cin >> h[i];
        region[h[i]].push_back(i);
        all[h[i]]++;
    }
    for(int i=1;i<=r;i++)
    {
        bigid[i]=-1;
        if(all[i]>=S)
        {
            big.push_back(i);
            bigid[i]=bigcnt++;
        }
    }
    dfs(1);
    while(q--)
    {
        int a,b;
        cin >> a >> b;
        int res=0;
        if(all[a]>=S&&all[b]>=S) res=bigres[bigid[a]][bigid[b]];
        else if(all[a]<S)
        {
            for(int x:region[a]) res+=qdown(b,tin[x],tout[x]);
        }
        else if(all[b]<S)
        {
            for(int x:region[b]) res+=qup(a,tin[x]);
        }
        cout << res << endl;
    }
    return 0;
}

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