oj.uz

Submission #852556

# Submission time Handle Problem Language Result Execution time Memory
852556 2023-09-22T05:21:41 Z abcvuitunggio Regions (IOI09_regions) C++17
75 / 100
 5111 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=55;
int n,R,q,r1,r2,cnt[200001][sz+1],c[25001][sz+1],c2[25001][sz+1],r[200001],p[200001],tin[200001],tout[200001],t,C[25001],pos[25001];
vector <int> ke[200001],ve[25001],V;
void dfs(int u){
    tin[u]=++t;
    ve[r[u]].push_back(t);
    if (pos[r[u]]<=sz)
        cnt[u][pos[r[u]]]++;
    for (int v:ke[u]){
        for (int i=1;i<=sz;i++)
            cnt[v][i]+=cnt[u][i];
        dfs(v);
    }
    for (int i=1;i<=sz;i++)
        c[r[u]][i]+=cnt[u][i];
    tout[u]=++t;
    ve[r[u]].push_back(-t);
}
void dfs2(int u){
    if (pos[r[u]]<=sz)
        cnt[u][pos[r[u]]]++;
    for (int v:ke[u]){
        dfs2(v);
        for (int i=1;i<=sz;i++)
            cnt[u][i]+=cnt[v][i];
    }
    for (int i=1;i<=sz;i++)
        c2[r[u]][i]+=cnt[u][i];
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> R >> q;
    for (int i=1;i<=n;i++){
        if (i>1){
            cin >> p[i];
            ke[p[i]].push_back(i);
        }
        cin >> r[i];
        C[r[i]]++;
    }
    for (int i=1;i<=R;i++)
        V.push_back(i);
    sort(V.begin(),V.end(),[](int i, int j){return C[i]<C[j];});
    for (int i=0;i<V.size();i++)
        pos[V[i]]=i+1;
    dfs(1);
    memset(cnt,0,sizeof(cnt));
    dfs2(1);
    while (q--){
        cin >> r1 >> r2;
        if (pos[r1]<=sz){
            cout << c[r2][pos[r1]] << endl;
            continue;
        }
        if (pos[r2]<=sz){
            cout << c2[r1][pos[r2]] << endl;
            continue;
        }
        int j=0,cnt=0,res=0;
        for (int i=0;i<ve[r2].size();i++){
            while (j<ve[r1].size()){
                if (abs(ve[r1][j])>abs(ve[r2][i]))
                    break;
                cnt+=(ve[r1][j]>0)-(ve[r1][j]<0);
                j++;
            }
            if (ve[r2][i]>0)
                res+=cnt;
        }
        cout << res << endl;
    }
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:47:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i=0;i<V.size();i++)
      |                  ~^~~~~~~~~
regions.cpp:63:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i=0;i<ve[r2].size();i++){
      |                      ~^~~~~~~~~~~~~~
regions.cpp:64:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 103512 KB Output is correct
2 Correct 12 ms 103256 KB Output is correct
3 Correct 13 ms 103508 KB Output is correct
4 Correct 15 ms 103512 KB Output is correct
5 Correct 15 ms 103512 KB Output is correct
6 Correct 20 ms 102744 KB Output is correct
7 Correct 22 ms 102744 KB Output is correct
8 Correct 25 ms 102744 KB Output is correct
9 Correct 36 ms 103256 KB Output is correct
10 Correct 61 ms 104048 KB Output is correct
11 Correct 72 ms 103540 KB Output is correct
12 Correct 83 ms 105000 KB Output is correct
13 Correct 117 ms 103836 KB Output is correct
14 Correct 137 ms 104424 KB Output is correct
15 Correct 142 ms 108168 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2882 ms 107652 KB Output is correct
2 Correct 4983 ms 106320 KB Output is correct
3 Correct 5111 ms 110008 KB Output is correct
4 Correct 170 ms 106472 KB Output is correct
5 Correct 234 ms 110804 KB Output is correct
6 Correct 513 ms 111696 KB Output is correct
7 Correct 708 ms 114896 KB Output is correct
8 Correct 721 ms 121284 KB Output is correct
9 Correct 1184 ms 125084 KB Output is correct
10 Runtime error 92 ms 131072 KB Execution killed with signal 9
11 Runtime error 129 ms 131072 KB Execution killed with signal 9
12 Correct 2206 ms 127212 KB Output is correct
13 Correct 2626 ms 128008 KB Output is correct
14 Correct 3030 ms 129472 KB Output is correct
15 Runtime error 117 ms 131072 KB Execution killed with signal 9
16 Runtime error 78 ms 131072 KB Execution killed with signal 9
17 Runtime error 70 ms 131072 KB Execution killed with signal 9