제출 #602338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602338		Quan2003	Regions (IOI09_regions)	C++17	45 / 100	4110 ms	42116 KiB

regions

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int sz=2e5+1;
const int block=500;
ll timer=1;
ll curr=1;
int n,q,m,k,r;
ll st[sz],en[sz];
ll a[sz];
vector<array<ll,2>>to[25001];
vector<ll>cmp[25001];
ll ans[500][25001];
ll up[17][sz];
ll dp[sz];
ll par[sz];
vector<ll>adj[sz];
struct compare {
 bool operator()(const array<ll,2>& value,
        const int& key)
 {
  return (value[0] < key);
 }
 bool operator()(const int& key,
     const array<ll,2>& value)
 {
  return (key < value[0]);
 }
};
const int mod=1e9+7;
void dfs(int u){
    to[a[u]].push_back({timer,u});
    st[u]=timer++;
    for(auto v:adj[u]){
        if(v==par[u]) continue;
        dfs(v);
    } en[u]=timer-1;
}
void dfs1(int u,int tar,int curr){
    if(a[u]==tar) curr++;
    ans[dp[tar]][a[u]]+=curr;
    for(auto v:adj[u]) dfs1(v,tar,curr);
}
int main(){
   cin>>n>>r>>q; 
   cin>>a[1];
   for(int i=2;i<=n;i++){
       cin>>par[i]>>a[i];
       adj[par[i]].push_back(i);
       cmp[a[i]].push_back(i);
    } 
   dfs(1);
   for(int i=1;i<=r;i++){
       if(cmp[i].size()<500) continue;
       dp[i]=curr++;
       dfs1(1,i,0);
   }
   for(int i=0;i<q;i++){
    ll u,w,res;cin>>u>>w;
    if(dp[u]>0) cout<<ans[dp[u]][a[w]]<<endl;
    else{
    const auto &p=to[w];res=0;  
    for(auto v:to[u]){
      int x=upper_bound(p.begin(),p.end(),en[v[1]],compare())-lower_bound(p.begin(),p.end(),st[v[1]],compare());
      res+=x;
       } cout<<res<<endl;
    }
  }
}

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