Submission #933382

#	Time	Username	Problem	Language	Result	Execution time	Memory
933382		NourWael	Regions (IOI09_regions)	C++17	95 / 100	8038 ms	37392 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];
vector<pair<int,int>> reg [mxR];

void dfs ( int i, int p ) {
     in[i] = t;
     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]});
}

void dfs2 ( int i, int p ) {
  for(int j=1; j<=r; j++) {
      if(region[i]==j) continue;
      fin[j][region[i]] += cnt[j];
     }
     cnt[region[i]]++;
     for(auto it:adj[i]){
      if(it==p) continue;
      dfs2(it,i);
     }
     cnt[region[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;
   }

   if(r>500) dfs(1,0);
   else dfs2(1,0);
   for(int i=1; i<=r; i++) sort(reg[i].begin(),reg[i].end());
   
   for(int i=0; i<q; i++) {
      int x,y; cin>>x>>y;
      int ans = 0;
      if(r<=500) { cout<<fin[x][y]<<endl; continue; }
      for(auto it:reg[x]) {
         int ind1 = lower_bound(reg[y].begin(),reg[y].end(), it ) - reg[y].begin();
         int ind2 = lower_bound(reg[y].begin(),reg[y].end(), make_pair(it.second, 0ll) ) - reg[y].begin();
         ans += ind2-ind1;
      }
      cout<<ans<<endl;
   }
  return 0;

}

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