Submission #933368

#	Time	Username	Problem	Language	Result	Execution time	Memory
933368		NourWael	Regions (IOI09_regions)	C++17	30 / 100	749 ms	38460 KiB

regions

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

void dfs ( int i, int p ) {

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

   dfs(1,0);

   for(int i=0; i<q; i++) {
      int x,y; cin>>x>>y;
      cout<<ans[x][y]<<endl;
   }
  return 0;

}

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