Submission #1189317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189317		akamizane	Regions (IOI09_regions)	C++17	100 / 100	2925 ms	34668 KiB

regions

#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
   int n, r, q;
   cin >> n >> r >> q;
   int timeDfs = 0;
   vector<int> a, tin, tout, ord, id;
   vector<vector<int>> calc, ad, comp;
   a.resize(n);
   ad.resize(n);
   tin.resize(n);
   tout.resize(n);
   ord.resize(n);
   comp.resize(r);
   id.assign(r, -1);
   cin >> a[0];
   a[0]--;
   for (int i = 1; i < n; i++){
      int p, h;
      cin >> p >> h;
      p--;
      h--;
      ad[p].push_back(i);
      a[i] = h;
   }
   for (int i = 0; i < r; i++) id[i] = -1;
   function<void(int)> tour = [&](int u) -> void {
      tin[u] = timeDfs++;
      ord[tin[u]] = u;
      comp[a[u]].push_back(tin[u]);
      for (int v : ad[u]) { tour(v); }
      tout[u] = timeDfs;
   };
   tour(0);
   int cur = 0;
   function<void(int, int, int)> dfs = [&](int u, int par_reg,
                                           int par_cnt) -> void {
      if (a[u] == par_reg) { par_cnt++; }
      calc[id[par_reg]][a[u]] += par_cnt;
      for (int v : ad[u]) { dfs(v, par_reg, par_cnt); }
   };
   const int block = sqrt(n);
   for (int i = 0; i < r; i++){
      if (comp[i].size() >= block){
         id[i] = cur++;
         calc.push_back(vector<int> (r));
         dfs(0, i, 0);
      }
   }
   while(q--){
      int e1, e2;
      cin >> e1 >> e2;
      e1--, e2--;
      if (comp[e1].size() >= block){
         cout << calc[id[e1]][e2] << "\n";
      }
      else{
         int ans = 0;
         for (auto u : comp[e1]){
            ans += lower_bound(comp[e2].begin(), comp[e2].end(), tout[ord[u]]) 
            - lower_bound(comp[e2].begin(), comp[e2].end(), tin[ord[u]]);

         }
         cout << ans << "\n";
      }
   }
   return 0;
}

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