oj.uz

Submission #852566

# Submission time Handle Problem Language Result Execution time Memory
852566 2023-09-22T05:49:21 Z abcvuitunggio Regions (IOI09_regions) C++17
50 / 100
 1181 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=416;
int n,R,q,r1,r2,cnt[200001][25000/sz+1],c[25001][25000/sz+1],c2[25001][25000/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<=25000;i++)
            cnt[v][i]+=cnt[u][i];
        dfs(v);
    }
    for (int i=1;i*sz<=25000;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<=25000;i++)
            cnt[u][i]+=cnt[v][i];
    }
    for (int i=1;i*sz<=25000;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 (ve[r1].empty()||ve[r2].empty()){
            cout << 0 << endl;
            continue;
        }
        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:ve[r2]){
            while (j<ve[r1].size()){
                if (abs(ve[r1][j])>abs(i))
                    break;
                cnt+=(ve[r1][j]>0)-(ve[r1][j]<0);
                j++;
            }
            if (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:68: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]
   68 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 110424 KB Output is correct
2 Correct 14 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 110424 KB Output is correct
7 Correct 26 ms 110424 KB Output is correct
8 Correct 34 ms 110424 KB Output is correct
9 Correct 35 ms 110932 KB Output is correct
10 Correct 56 ms 110916 KB Output is correct
11 Correct 78 ms 111360 KB Output is correct
12 Correct 81 ms 112108 KB Output is correct
13 Correct 112 ms 111660 KB Output is correct
14 Correct 143 ms 112244 KB Output is correct
15 Correct 179 ms 116112 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 116224 KB Output is correct
2 Correct 627 ms 114888 KB Output is correct
3 Correct 1181 ms 117828 KB Output is correct
4 Correct 175 ms 116348 KB Output is correct
5 Correct 238 ms 118624 KB Output is correct
6 Correct 349 ms 122356 KB Output is correct
7 Correct 617 ms 124760 KB Output is correct
8 Incorrect 555 ms 130000 KB Output isn't correct
9 Runtime error 98 ms 131072 KB Execution killed with signal 9
10 Runtime error 100 ms 131072 KB Execution killed with signal 9
11 Runtime error 122 ms 131072 KB Execution killed with signal 9
12 Runtime error 162 ms 131072 KB Execution killed with signal 9
13 Runtime error 121 ms 131072 KB Execution killed with signal 9
14 Runtime error 136 ms 131072 KB Execution killed with signal 9
15 Runtime error 66 ms 131072 KB Execution killed with signal 9
16 Runtime error 78 ms 131072 KB Execution killed with signal 9
17 Runtime error 72 ms 131072 KB Execution killed with signal 9