oj.uz

Submission #1007572

# Submission time Handle Problem Language Result Execution time Memory
1007572 2024-06-25T08:03:45 Z huutuan Regions (IOI09_regions) C++14
85 / 100
 6162 ms 131072 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=2e5+10, S=3000;
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 5 ms 14680 KB Output is correct
5 Correct 6 ms 14680 KB Output is correct
6 Correct 9 ms 14680 KB Output is correct
7 Correct 18 ms 14680 KB Output is correct
8 Correct 19 ms 14936 KB Output is correct
9 Correct 30 ms 15448 KB Output is correct
10 Correct 60 ms 15192 KB Output is correct
11 Correct 111 ms 15448 KB Output is correct
12 Correct 123 ms 15960 KB Output is correct
13 Correct 197 ms 15448 KB Output is correct
14 Correct 341 ms 15960 KB Output is correct
15 Correct 325 ms 19800 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1755 ms 60216 KB Output is correct
2 Correct 2153 ms 59984 KB Output is correct
3 Correct 3107 ms 70744 KB Output is correct
4 Correct 292 ms 15960 KB Output is correct
5 Correct 376 ms 18264 KB Output is correct
6 Correct 2020 ms 17272 KB Output is correct
7 Correct 2463 ms 18084 KB Output is correct
8 Correct 2097 ms 24664 KB Output is correct
9 Correct 3399 ms 22800 KB Output is correct
10 Correct 6162 ms 29776 KB Output is correct
11 Correct 5638 ms 21764 KB Output is correct
12 Correct 1493 ms 125916 KB Output is correct
13 Correct 2132 ms 126800 KB Output is correct
14 Correct 4210 ms 128336 KB Output is correct
15 Runtime error 65 ms 131072 KB Execution killed with signal 9
16 Runtime error 62 ms 131072 KB Execution killed with signal 9
17 Runtime error 59 ms 131072 KB Execution killed with signal 9