oj.uz

Submission #1007571

# Submission time Handle Problem Language Result Execution time Memory
1007571 2024-06-25T08:03:31 Z huutuan Regions (IOI09_regions) C++14
8 / 100
 20 ms 20636 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=2000+10, S=2;
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
8.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 5 ms 10840 KB Output is correct
5 Correct 5 ms 10840 KB Output is correct
6 Correct 10 ms 14936 KB Output is correct
7 Correct 16 ms 19032 KB Output is correct
8 Correct 20 ms 20312 KB Output is correct
9 Incorrect 6 ms 20568 KB Unexpected end of file - int32 expected
10 Incorrect 4 ms 16216 KB Unexpected end of file - int32 expected
11 Incorrect 5 ms 20488 KB Unexpected end of file - int32 expected
12 Incorrect 5 ms 20564 KB Unexpected end of file - int32 expected
13 Incorrect 4 ms 20312 KB Unexpected end of file - int32 expected
14 Incorrect 4 ms 20380 KB Unexpected end of file - int32 expected
15 Incorrect 5 ms 20636 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 20312 KB Unexpected end of file - int32 expected
2 Incorrect 5 ms 19800 KB Unexpected end of file - int32 expected
3 Incorrect 5 ms 20312 KB Unexpected end of file - int32 expected
4 Runtime error 2 ms 852 KB Execution killed with signal 6
5 Runtime error 2 ms 856 KB Execution killed with signal 6
6 Runtime error 2 ms 1112 KB Execution killed with signal 6
7 Runtime error 1 ms 856 KB Execution killed with signal 11
8 Runtime error 1 ms 856 KB Execution killed with signal 11
9 Runtime error 1 ms 600 KB Execution killed with signal 11
10 Runtime error 1 ms 600 KB Execution killed with signal 11
11 Runtime error 1 ms 600 KB Execution killed with signal 11
12 Runtime error 1 ms 600 KB Execution killed with signal 11
13 Runtime error 1 ms 600 KB Execution killed with signal 11
14 Runtime error 1 ms 600 KB Execution killed with signal 11
15 Runtime error 1 ms 600 KB Execution killed with signal 11
16 Runtime error 1 ms 600 KB Execution killed with signal 11
17 Runtime error 1 ms 600 KB Execution killed with signal 11