oj.uz

답안 #1007563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1007563 2024-06-25T07:52:13 Z huutuan Regions (IOI09_regions) C++14
55 / 100
 6043 ms 131072 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=2e5+10, S=600;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 3 ms 14792 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 14936 KB Output is correct
7 Correct 22 ms 14680 KB Output is correct
8 Correct 21 ms 14936 KB Output is correct
9 Correct 32 ms 15448 KB Output is correct
10 Correct 65 ms 15192 KB Output is correct
11 Correct 116 ms 15448 KB Output is correct
12 Correct 124 ms 15960 KB Output is correct
13 Correct 213 ms 15448 KB Output is correct
14 Correct 367 ms 15960 KB Output is correct
15 Correct 372 ms 19800 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 131072 KB Execution killed with signal 9
2 Runtime error 37 ms 131072 KB Execution killed with signal 9
3 Runtime error 31 ms 131072 KB Execution killed with signal 9
4 Correct 340 ms 15960 KB Output is correct
5 Correct 353 ms 18520 KB Output is correct
6 Correct 1942 ms 17384 KB Output is correct
7 Correct 2431 ms 18008 KB Output is correct
8 Correct 1976 ms 24664 KB Output is correct
9 Correct 3353 ms 22864 KB Output is correct
10 Correct 6043 ms 29776 KB Output is correct
11 Correct 5799 ms 21828 KB Output is correct
12 Runtime error 49 ms 131072 KB Execution killed with signal 9
13 Runtime error 42 ms 131072 KB Execution killed with signal 9
14 Runtime error 69 ms 131072 KB Execution killed with signal 9
15 Runtime error 41 ms 131072 KB Execution killed with signal 9
16 Runtime error 47 ms 131072 KB Execution killed with signal 9
17 Runtime error 49 ms 131072 KB Execution killed with signal 9