제출 #928280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928280		noyancanturk	Regions (IOI09_regions)	C++17	100 / 100	4210 ms	54288 KiB

regions

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+100;
#else
    const int lim=3e3+3;
#endif

#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int mod=1e9+7;
//const int mod=(1ll<<61)-1;

using pii=pair<int,int>;

const int rlim=25100;

int tribe[lim],parent[lim];
vector<int>v[lim],tr[rlim];
int tin[lim],tout[lim],hastin[lim],tt=1;
unordered_map<int,int>anss[lim];

void tour(int node){
    hastin[tin[node]=tt++]=node;
    for(int j:v[node]){
        tour(j);
    }
    tout[node]=tt;
}

inline void solve(){
    int n,r,q;
    cin>>n>>r>>q;
    cin>>tribe[1];
    tr[tribe[1]].pb(1);
    for(int i=2;i<=n;i++){
        cin>>parent[i];
        v[parent[i]].pb(i);
        cin>>tribe[i];
        tr[tribe[i]].pb(i);
    }
    tour(1);
    for(int i=1;i<=r;i++){
        sort(tr[i].begin(),tr[i].end(),
        [&](int x,int y) -> bool {
            return tin[x]<tin[y];
        });
        if(500<=tr[i].size()){
            int dif[n+5];
            memset(dif,0,sizeof(dif));
            for(int j:tr[i]){
                dif[tin[j]]++;
                dif[tout[j]]--;
            }
            int cur=0;
            for(int j=1;j<=tt;j++){
                cur+=dif[j];
                anss[i][tribe[hastin[j]]]+=cur;
            }
        }
    }
    while(q--){
        int a,b;
        cin>>a>>b;
        if(tr[a].size()<=500){
            int ans=0;
            for(int j:tr[a]){
                int l=0,r=tr[b].size()-1,first=-1,last=-1;
                while(l<=r){
                    int mid=(l+r)>>1;
                    if(tin[j]<tin[tr[b][mid]]){
                        first=mid;
                        r=mid-1;
                    }else{
                        l=mid+1;
                    }
                }
                if(first==-1){
                    continue;
                }
                l=first,r=tr[b].size()-1;
                while(l<=r){
                    int mid=(l+r)>>1;
                    if(tin[tr[b][mid]]<tout[j]){
                        last=mid;
                        l=mid+1;
                    }else{
                        r=mid-1;
                    }
                }
                if(first<=last){
                    ans+=last-first+1;
                }
            }
            cout<<ans<<endl;
        }else{
            cout<<anss[a][b]<<endl;
        }
        cout.flush();
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

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