제출 #1301800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301800		sash01	Regions (IOI09_regions)	C++20	1 / 100	2373 ms	37112 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=1,ans[450][25001],to[200001],t[200001],colour;
vector <int> v[232109],big;
vector <pair <int,int>> r[262144];
void speed()
{
 ios_base::sync_with_stdio(false);
 cin.tie(0);
}
void dfs(int beg,int par)
{
    pair <int,int> pb;
    pb.first=tt++;
    for(auto nb:v[beg])
    {
        if(nb!=par)dfs(nb,beg);
    }
    pb.second=tt++;
    r[h[beg]].push_back(pb);
}
void dfs_(int beg,int par,int brr)
{
    for(auto nb:v[beg])
    {
        if(nb!=par)
        {
            if(h[beg]==colour)dfs_(nb,beg,brr+1);
            else dfs_(nb,beg,brr);
        }
    }
    ans[colour][h[beg]]+=brr;
}
int bin1(pair <int,int> p,int y)
{
    int left=0,right=r[y].size()-1,mid,ans=1e9;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(r[y][mid].first>p.first)
        {
            ans=mid;
            right=mid-1;
        }
        else left=mid+1;
    }
    return ans;
}
int bin2(pair <int,int> p,int y)
{
    int left=0,right=r[y].size()-1,mid,ans=-1e9;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(r[y][mid].second<p.second)
        {
            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++)
    {
        if(r[i].size()>=450)
        {
            big.push_back(i);
            to[i]=big.size()-1;
        }
    }
    for(int i=0;i<big.size();i++)
    {
        colour=i;
        dfs_(1,-1,0);
    }
    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(r[r1].size()>=450)
        {
            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);
                ans+=max(i2-i1+1,0LL);
            }
            cout<<ans<<endl;
        }
        cout.flush();
    }
    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: 1 / 15
• Subtask 2: 0 / 85