oj.uz

Submission #1007565

# Submission time Handle Problem Language Result Execution time Memory
1007565 2024-06-25T07:54:41 Z huutuan Regions (IOI09_regions) C++14
55 / 100
 5773 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[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 4 ms 14680 KB Output is correct
5 Correct 6 ms 14680 KB Output is correct
6 Correct 11 ms 14680 KB Output is correct
7 Correct 19 ms 14680 KB Output is correct
8 Correct 20 ms 14936 KB Output is correct
9 Correct 26 ms 15448 KB Output is correct
10 Correct 52 ms 15192 KB Output is correct
11 Correct 100 ms 15448 KB Output is correct
12 Correct 116 ms 15960 KB Output is correct
13 Correct 191 ms 15448 KB Output is correct
14 Correct 372 ms 15960 KB Output is correct
15 Correct 325 ms 19800 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1749 ms 60224 KB Output isn't correct
2 Incorrect 2078 ms 59992 KB Output isn't correct
3 Incorrect 2871 ms 70988 KB Output isn't correct
4 Correct 316 ms 15960 KB Output is correct
5 Correct 315 ms 18520 KB Output is correct
6 Correct 1814 ms 17240 KB Output is correct
7 Correct 2301 ms 18008 KB Output is correct
8 Correct 1921 ms 24664 KB Output is correct
9 Correct 3198 ms 22792 KB Output is correct
10 Correct 5773 ms 29752 KB Output is correct
11 Correct 5648 ms 21760 KB Output is correct
12 Incorrect 1373 ms 125776 KB Output isn't correct
13 Incorrect 2013 ms 126800 KB Output isn't correct
14 Incorrect 4292 ms 128256 KB Output isn't correct
15 Runtime error 59 ms 131072 KB Execution killed with signal 9
16 Runtime error 76 ms 131072 KB Execution killed with signal 9
17 Runtime error 65 ms 131072 KB Execution killed with signal 9