Submission #1007564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007564		huutuan	Regions (IOI09_regions)	C++14	55 / 100	6179 ms	131072 KiB

regions

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+10, S=1000;
int n, r, q, type[N], par[N], cnt[N], sum2[N][N/S+10], id[N], sum1[N][N/S+10], ans[N/S+10][N/S+10];
vector<int> g[N], vv[N];
int cnt_heavy, tdfs, tin[N], tout[N];

void dfs(int u){
   tin[u]=++tdfs;
   for (int i=1; i<=cnt_heavy; ++i){
      sum2[u][i]=sum2[par[u]][i];
   }
   if (id[type[u]]) ++sum2[u][id[type[u]]];
   for (int v:g[u]){
      dfs(v);
      for (int i=1; i<=cnt_heavy; ++i) sum1[u][i]+=sum1[v][i];
   }
   if (id[type[u]]){
      ++sum1[u][id[type[u]]];
      for (int i=1; i<=cnt_heavy; ++i) if (i!=id[type[u]]) ans[u][i]+=sum1[u][i];
   }
   tout[u]=tdfs;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> r >> q;
   cin >> type[1]; ++cnt[type[1]];
   vv[type[1]].push_back(1);
   for (int i=2; i<=n; ++i){
      cin >> par[i] >> type[i]; ++cnt[type[i]];
      vv[type[i]].push_back(i);
      g[par[i]].push_back(i);
   }
   for (int i=1; i<=r; ++i) if (cnt[i]>S) id[i]=++cnt_heavy;
   dfs(1);
   while (q--){
      int r1, r2; cin >> r1 >> r2;
      if (id[r1] && id[r2]){
         cout << ans[id[r1]][id[r2]] << endl;
      }else if (id[r1]){
         int sum=0;
         for (int i:vv[r2]) sum+=sum2[i][id[r1]];
         cout << sum << endl;
      }else if (id[r2]){
         int sum=0;
         for (int i:vv[r1]) sum+=sum1[i][id[r2]];
         cout << sum << endl;
      }else{
         vector<pair<int, int>> v;
         for (int i:vv[r1]) v.emplace_back(tin[i], -1);
         for (int i:vv[r1]) v.emplace_back(tout[i], 1);
         for (int i:vv[r2]) v.emplace_back(tin[i], 0);
         sort(v.begin(), v.end());
         int sum=0, add=0;
         for (auto &i:v){
            if (i.second==0) sum+=add;
            else add-=i.second;
         }
         cout << sum << endl;
      }
   }
   return 0;
}

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