oj.uz

Submission #1007562

# Submission time Handle Problem Language Result Execution time Memory
1007562 2024-06-25T07:51:13 Z huutuan Regions (IOI09_regions) C++14
55 / 100
 5970 ms 131072 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=2e5+10, S=500;
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.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 2 ms 14680 KB Output is correct
4 Correct 5 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 20 ms 14680 KB Output is correct
8 Correct 23 ms 14936 KB Output is correct
9 Correct 31 ms 15448 KB Output is correct
10 Correct 62 ms 15192 KB Output is correct
11 Correct 117 ms 15448 KB Output is correct
12 Correct 123 ms 15960 KB Output is correct
13 Correct 201 ms 15448 KB Output is correct
14 Correct 349 ms 16216 KB Output is correct
15 Correct 346 ms 19800 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 131072 KB Execution killed with signal 9
2 Runtime error 39 ms 131072 KB Execution killed with signal 9
3 Runtime error 48 ms 131072 KB Execution killed with signal 9
4 Correct 310 ms 16216 KB Output is correct
5 Correct 334 ms 18520 KB Output is correct
6 Correct 1842 ms 17368 KB Output is correct
7 Correct 2222 ms 18264 KB Output is correct
8 Correct 2007 ms 24920 KB Output is correct
9 Correct 3223 ms 23120 KB Output is correct
10 Correct 5730 ms 30032 KB Output is correct
11 Correct 5970 ms 21952 KB Output is correct
12 Runtime error 52 ms 131072 KB Execution killed with signal 9
13 Runtime error 48 ms 131072 KB Execution killed with signal 9
14 Runtime error 45 ms 131072 KB Execution killed with signal 9
15 Runtime error 56 ms 131072 KB Execution killed with signal 9
16 Runtime error 56 ms 131072 KB Execution killed with signal 9
17 Runtime error 47 ms 131072 KB Execution killed with signal 9