제출 #933436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933436		NourWael	Regions (IOI09_regions)	C++17	80 / 100	8054 ms	102096 KiB

regions

#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 2e5+5;
int  const mxR = 25005;
vector<int> adj [mxN];
int in[mxN], out[mxN], t, r , n, region[mxN], q, fin[505][505], cnt[505], power[mxR];
vector<pair<int,int>> reg [mxR], ori[mxR];
vector<vector<int>> seg [mxR];

void build ( int node, int l, int r , int i) {
   if(l==r-1) { seg[i][node].push_back(reg[i][l].second); return ; }
   int m = (l+r)/2;
   build(node*2+1, l, m, i), build(node*2+2, m, r, i);
   seg[i][node] = seg[i][node*2+1];
   for(auto it:seg[i][node*2+2]) seg[i][node].push_back(it);
   sort(seg[i][node].begin(),seg[i][node].end());
}

int get ( int node, int l, int r, int i, int ind , int val) {
   if(l>=ind) return 0;
   if(r<=ind) {
      int tot = seg[i][node].size();
      int smaller = lower_bound(seg[i][node].begin(), seg[i][node].end(), val ) - seg[i][node].begin();
      return tot - smaller;
   }
   int m = (l+r)/2;
   return get(node*2+1, l, m, i, ind, val) + get(node*2+2, m, r, i, ind, val);
}

void dfs ( int i, int p ) {
     t++, in[i] = t;
     for(auto it:adj[i]){
      if(it==p) continue;
      dfs(it,i);
     }
     t++, out[i] = t;
     reg[region[i]].push_back({in[i],out[i]});
}

signed main() {
   
   ios_base:: sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

   cin>>n>>r>>q>>region[1];
   for(int i=2; i<=n; i++) {
      int k, h; cin>>k>>h;
      adj[i].push_back(k), adj[k].push_back(i);
      region[i] = h;
   }

   dfs(1,0);
   for(int i=1; i<=r; i++) {
      sort(reg[i].begin(),reg[i].end());
      ori[i] = reg[i];
      int pw = (1<<(__lg(reg[i].size()-1)+1));
      power[i] = pw;
      for(int j=reg[i].size(); j<=pw; j++) reg[i].push_back({0,0});
      seg[i].resize(4*pw+5);
      build(0,0,pw, i);
   }
  for(int i=0; i<q; i++) {
      int x,y; cin>>x>>y;
      int ans = 0;
      if(ori[x].size()<=ori[y].size()) {
        for(auto it:ori[x]) {
           int ind1 = lower_bound(ori[y].begin(),ori[y].end(), it ) - ori[y].begin();
           int ind2 = lower_bound(ori[y].begin(),ori[y].end(), make_pair(it.second, 0ll) ) - ori[y].begin();
           ans += ind2-ind1;
        }
         cout<<ans<<endl; continue;
      }

      for(auto it:ori[y]){
         int ind = lower_bound(ori[x].begin(),ori[x].end(), it ) - ori[x].begin();
        ans+=get(0,0,power[x], x, ind, it.second);
      }
     cout<<ans<<endl;
   }
  return 0;

}

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