oj.uz

Submission #852560

# Submission time Handle Problem Language Result Execution time Memory
852560 2023-09-22T05:33:50 Z abcvuitunggio Regions (IOI09_regions) C++17
16 / 100
 789 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=60;
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 (C[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 (C[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 (C[r1]>sz){
            cout << c[r2][pos[r1]] << endl;
            continue;
        }
        if (C[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
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 110424 KB Output is correct
2 Correct 15 ms 110424 KB Output is correct
3 Correct 14 ms 110424 KB Output is correct
4 Correct 16 ms 110424 KB Output is correct
5 Correct 17 ms 110424 KB Output is correct
6 Correct 22 ms 110488 KB Output is correct
7 Correct 27 ms 110424 KB Output is correct
8 Correct 30 ms 110680 KB Output is correct
9 Correct 43 ms 110936 KB Output is correct
10 Correct 65 ms 110936 KB Output is correct
11 Incorrect 69 ms 111360 KB Output isn't correct
12 Correct 91 ms 111988 KB Output is correct
13 Incorrect 89 ms 112416 KB Output isn't correct
14 Incorrect 94 ms 112996 KB Output isn't correct
15 Incorrect 113 ms 116712 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 452 ms 116224 KB Output isn't correct
2 Incorrect 555 ms 114884 KB Output isn't correct
3 Incorrect 789 ms 118580 KB Output isn't correct
4 Incorrect 142 ms 117100 KB Output isn't correct
5 Incorrect 224 ms 118620 KB Output isn't correct
6 Correct 385 ms 122168 KB Output is correct
7 Incorrect 543 ms 124760 KB Output isn't correct
8 Incorrect 548 ms 129988 KB Output isn't correct
9 Runtime error 101 ms 131072 KB Execution killed with signal 9
10 Runtime error 93 ms 131072 KB Execution killed with signal 9
11 Runtime error 119 ms 131072 KB Execution killed with signal 9
12 Runtime error 138 ms 131072 KB Execution killed with signal 9
13 Runtime error 109 ms 131072 KB Execution killed with signal 9
14 Runtime error 126 ms 131072 KB Execution killed with signal 9
15 Runtime error 63 ms 131072 KB Execution killed with signal 9
16 Runtime error 71 ms 131072 KB Execution killed with signal 9
17 Runtime error 73 ms 131072 KB Execution killed with signal 9