제출 #591852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591852		Quan2003	Regions (IOI09_regions)	C++17	70 / 100	8093 ms	30216 KiB

regions

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

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