oj.uz

Submission #1007573

# Submission time Handle Problem Language Result Execution time Memory
1007573 2024-06-25T08:04:57 Z huutuan Regions (IOI09_regions) C++14
100 / 100
 5946 ms 121424 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=2e5+10, S=4000;
int n, r, q, type[N], par[N], cnt[N], sum2[N][N/S+2], id[N], sum1[N][N/S+2], ans[N/S+2][N/S+2];
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[id[type[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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 3 ms 14680 KB Output is correct
4 Correct 4 ms 14680 KB Output is correct
5 Correct 6 ms 14680 KB Output is correct
6 Correct 11 ms 14936 KB Output is correct
7 Correct 18 ms 14680 KB Output is correct
8 Correct 20 ms 14936 KB Output is correct
9 Correct 36 ms 15448 KB Output is correct
10 Correct 74 ms 15192 KB Output is correct
11 Correct 123 ms 15448 KB Output is correct
12 Correct 135 ms 15960 KB Output is correct
13 Correct 205 ms 15704 KB Output is correct
14 Correct 358 ms 15960 KB Output is correct
15 Correct 352 ms 20312 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1728 ms 49496 KB Output is correct
2 Correct 2148 ms 52356 KB Output is correct
3 Correct 3264 ms 59224 KB Output is correct
4 Correct 357 ms 16216 KB Output is correct
5 Correct 340 ms 18776 KB Output is correct
6 Correct 1983 ms 17240 KB Output is correct
7 Correct 2459 ms 18008 KB Output is correct
8 Correct 1798 ms 25432 KB Output is correct
9 Correct 3275 ms 22816 KB Output is correct
10 Correct 5946 ms 30800 KB Output is correct
11 Correct 5841 ms 21376 KB Output is correct
12 Correct 1390 ms 101200 KB Output is correct
13 Correct 1974 ms 102224 KB Output is correct
14 Correct 4098 ms 103320 KB Output is correct
15 Correct 3546 ms 110292 KB Output is correct
16 Correct 3223 ms 121424 KB Output is correct
17 Correct 4108 ms 119120 KB Output is correct