제출 #1301813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301813		sash01	Regions (IOI09_regions)	C++20	0 / 100	337 ms	43112 KiB

regions

#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <set>
#include <cstring>
#define control cout<<"e ne"<<endl;
#define endl '\n'
#define int long long
using namespace std;
int n,R,q,h[231072],s,r1,r2,tt,ans[450][25001],to[200001],t[200001],colour,in[200001],out[200001];
vector <int> v[232109],big;
vector <int> r[262144];
void speed()
{
 ios_base::sync_with_stdio(false);
 cin.tie(0);
}
bool cmp(int x,int y)
{
    return in[x]<in[y];
}
void dfs(int beg,int par)
{
    pair <int,int> pb;
    in[beg]=++tt;
    for(auto nb:v[beg])
    {
        if(nb!=par)dfs(nb,beg);
    }
    out[beg]=++tt;
    r[h[beg]].push_back(beg);
}
void dfs_(int beg,int par,int brr)
{
    for(auto nb:v[beg])
    {
        if(nb!=par)
        {
            if(to[h[beg]]==colour)dfs_(nb,beg,brr+1);
            else dfs_(nb,beg,brr);
        }
    }
    ans[colour][h[beg]]+=brr;
}
int bin1(int p,int y)
{
    int left=0,right=r[y].size()-1,mid,ans=1e9;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(in[r[y][mid]]>in[p])
        {
            ans=mid;
            right=mid-1;
        }
        else left=mid+1;
    }
    return ans;
}
int bin2(int p,int y)
{
    int left=0,right=r[y].size()-1,mid,ans=-1e9;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(out[r[y][mid]]<out[p])
        {
            ans=mid;
            left=mid+1;
        }
        else right=mid-1;
    }
    return ans;
}
signed main()
{
    /*
    #ifdef ONLINE_JUDGE
    freopen("txt.in","r",stdin)
    freopen("txt.out","w",stdout)
    #endif
    */
    speed();
    cin>>n>>R>>q>>h[1];
    for(int i=2;i<=n;i++)
    {
        cin>>s>>h[i];
        v[s].push_back(i);
    }
    dfs(1,-1);
    for(int i=1;i<=R;i++)
    {
        sort(r[i].begin(),r[i].end(),cmp);
        if(r[i].size()>=sqrt(n))
        {
            big.push_back(i);
            to[i]=big.size();
        }
    }
    for(int i=0;i<big.size();i++)
    {
        colour=i+1;
        dfs_(1,-1,0);
    }
    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(r[r1].size()>=sqrt(n))
        {
            int x=to[r1];
            cout<<ans[x][r2]<<endl;
        }
        else
        {
            int ans=0;
            for(auto i:r[r1])
            {
                int i1=bin1(i,r2),i2=bin2(i,r2);
                if(i1!=1e9&&i2!=-1e9)ans+=max(i2-i1+1,0LL);
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}
/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
*/

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