Submission #1189310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189310		akamizane	Regions (IOI09_regions)	C++17	0 / 100	307 ms	45124 KiB

regions

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

#define debug(...) 42


#define int long long
using ll = long long;

int timeDfs = 0;
vector<int> a, tin, tout, ord, id;
vector<vector<int>> calc, ad, comp;

void tour(int u){
   tin[u] = timeDfs++;
   ord[tin[u]] = u;
   comp[a[u]].push_back(tin[u]);
   for (auto v : ad[u]) tour(v);
   tout[u] = timeDfs;
}

void dfs(int u, int par_reg, int par_cnt){
   if (a[u] == par_reg) par_cnt++;
   calc[id[par_reg]][a[u]] += par_cnt;
   for (auto v : ad[u]) dfs(v, par_reg, par_cnt);
}

void solve(){
   int n, r, q;
   cin >> n >> r >> q;
   a.resize(n);
   ad.resize(n);
   tin.resize(n);
   tout.resize(n);
   ord.resize(n);
   comp.resize(n);
   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;
   tour(0);
   int cur = 0;
   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";
      }
   }
}

int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   int tt = 1;
   // cin >> tt;
   while(tt--) {
      solve();
   }
   return 0;
}

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