oj.uz

Submission #852568

# Submission time Handle Problem Language Result Execution time Memory
852568 2023-09-22T05:57:44 Z abcvuitunggio Regions (IOI09_regions) C++17
85 / 100
 1744 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=3600;
int lim,n,R,q,r1,r2,cnt[200001][200000/sz+1],c[25001][200000/sz+1],c2[25001][200000/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<=lim;i++)
            cnt[v][i]+=cnt[u][i];
        dfs(v);
    }
    for (int i=1;i<=lim;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<=lim;i++)
            cnt[u][i]+=cnt[v][i];
    }
    for (int i=1;i<=lim;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;
        if (C[V[i]]>sz)
            lim=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:71: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]
   71 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 99224 KB Output is correct
2 Correct 12 ms 99160 KB Output is correct
3 Correct 13 ms 99160 KB Output is correct
4 Correct 13 ms 99416 KB Output is correct
5 Correct 14 ms 99288 KB Output is correct
6 Correct 23 ms 99416 KB Output is correct
7 Correct 26 ms 99380 KB Output is correct
8 Correct 27 ms 99416 KB Output is correct
9 Correct 33 ms 99924 KB Output is correct
10 Correct 49 ms 101976 KB Output is correct
11 Correct 71 ms 102336 KB Output is correct
12 Correct 79 ms 102952 KB Output is correct
13 Correct 102 ms 102744 KB Output is correct
14 Correct 130 ms 103220 KB Output is correct
15 Correct 175 ms 106936 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 108500 KB Output is correct
2 Correct 726 ms 107160 KB Output is correct
3 Correct 1151 ms 110008 KB Output is correct
4 Correct 142 ms 103212 KB Output is correct
5 Correct 192 ms 105488 KB Output is correct
6 Correct 540 ms 104360 KB Output is correct
7 Correct 673 ms 105472 KB Output is correct
8 Correct 674 ms 112084 KB Output is correct
9 Correct 1031 ms 111884 KB Output is correct
10 Correct 1744 ms 117728 KB Output is correct
11 Correct 1726 ms 110828 KB Output is correct
12 Correct 704 ms 128064 KB Output is correct
13 Correct 923 ms 128856 KB Output is correct
14 Correct 1157 ms 129360 KB Output is correct
15 Runtime error 89 ms 131072 KB Execution killed with signal 9
16 Runtime error 76 ms 131072 KB Execution killed with signal 9
17 Runtime error 70 ms 131072 KB Execution killed with signal 9