oj.uz

Submission #852567

# Submission time Handle Problem Language Result Execution time Memory
852567 2023-09-22T05:56:31 Z abcvuitunggio Regions (IOI09_regions) C++17
70 / 100
 1744 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=3333;
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 15 ms 107096 KB Output is correct
2 Correct 13 ms 107096 KB Output is correct
3 Correct 13 ms 107096 KB Output is correct
4 Correct 14 ms 106928 KB Output is correct
5 Correct 15 ms 107092 KB Output is correct
6 Correct 20 ms 107080 KB Output is correct
7 Correct 29 ms 107096 KB Output is correct
8 Correct 37 ms 107096 KB Output is correct
9 Correct 39 ms 107608 KB Output is correct
10 Correct 72 ms 109656 KB Output is correct
11 Correct 78 ms 110056 KB Output is correct
12 Correct 88 ms 110680 KB Output is correct
13 Correct 93 ms 110460 KB Output is correct
14 Correct 121 ms 110948 KB Output is correct
15 Correct 186 ms 114688 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 116220 KB Output is correct
2 Correct 679 ms 114880 KB Output is correct
3 Correct 1163 ms 117840 KB Output is correct
4 Correct 145 ms 110940 KB Output is correct
5 Correct 211 ms 113220 KB Output is correct
6 Correct 493 ms 111984 KB Output is correct
7 Correct 652 ms 113208 KB Output is correct
8 Correct 652 ms 119772 KB Output is correct
9 Correct 1016 ms 119516 KB Output is correct
10 Correct 1744 ms 125420 KB Output is correct
11 Correct 1622 ms 118396 KB Output is correct
12 Runtime error 86 ms 131072 KB Execution killed with signal 9
13 Runtime error 81 ms 131072 KB Execution killed with signal 9
14 Runtime error 98 ms 131072 KB Execution killed with signal 9
15 Runtime error 56 ms 131072 KB Execution killed with signal 9
16 Runtime error 75 ms 131072 KB Execution killed with signal 9
17 Runtime error 63 ms 131072 KB Execution killed with signal 9