oj.uz

Submission #1007564

# Submission time Handle Problem Language Result Execution time Memory
1007564 2024-06-25T07:53:26 Z huutuan Regions (IOI09_regions) C++14
55 / 100
 6179 ms 131072 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16812 KB Output is correct
3 Correct 3 ms 16816 KB Output is correct
4 Correct 4 ms 16728 KB Output is correct
5 Correct 5 ms 16728 KB Output is correct
6 Correct 10 ms 16984 KB Output is correct
7 Correct 18 ms 16728 KB Output is correct
8 Correct 20 ms 16984 KB Output is correct
9 Correct 33 ms 17240 KB Output is correct
10 Correct 67 ms 17240 KB Output is correct
11 Correct 130 ms 17496 KB Output is correct
12 Correct 124 ms 18008 KB Output is correct
13 Correct 201 ms 17496 KB Output is correct
14 Correct 357 ms 18008 KB Output is correct
15 Correct 357 ms 21592 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 131072 KB Execution killed with signal 9
2 Runtime error 31 ms 131072 KB Execution killed with signal 9
3 Runtime error 33 ms 131072 KB Execution killed with signal 9
4 Correct 335 ms 18008 KB Output is correct
5 Correct 310 ms 20312 KB Output is correct
6 Correct 1944 ms 19032 KB Output is correct
7 Correct 2533 ms 19544 KB Output is correct
8 Correct 2041 ms 26200 KB Output is correct
9 Correct 3320 ms 23896 KB Output is correct
10 Correct 6179 ms 30800 KB Output is correct
11 Correct 5650 ms 22620 KB Output is correct
12 Runtime error 61 ms 131072 KB Execution killed with signal 9
13 Runtime error 49 ms 131072 KB Execution killed with signal 9
14 Runtime error 58 ms 131072 KB Execution killed with signal 9
15 Runtime error 48 ms 131072 KB Execution killed with signal 9
16 Runtime error 53 ms 131072 KB Execution killed with signal 9
17 Runtime error 51 ms 131072 KB Execution killed with signal 9