oj.uz

Submission #852565

# Submission time Handle Problem Language Result Execution time Memory
852565 2023-09-22T05:44:53 Z abcvuitunggio Regions (IOI09_regions) C++17
30 / 100
 1183 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<=R;i++)
            cnt[v][i]+=cnt[u][i];
        dfs(v);
    }
    for (int i=1;i*sz<=R;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<=R;i++)
            cnt[u][i]+=cnt[v][i];
    }
    for (int i=1;i*sz<=R;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 14 ms 107096 KB Output is correct
2 Correct 13 ms 107096 KB Output is correct
3 Correct 14 ms 107096 KB Output is correct
4 Correct 14 ms 106896 KB Output is correct
5 Correct 15 ms 106948 KB Output is correct
6 Correct 20 ms 107096 KB Output is correct
7 Correct 25 ms 107096 KB Output is correct
8 Correct 26 ms 107096 KB Output is correct
9 Correct 38 ms 107608 KB Output is correct
10 Correct 59 ms 111032 KB Output is correct
11 Correct 68 ms 110080 KB Output is correct
12 Correct 83 ms 111972 KB Output is correct
13 Correct 115 ms 110356 KB Output is correct
14 Correct 139 ms 110944 KB Output is correct
15 Correct 188 ms 114668 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 560 ms 114180 KB Output isn't correct
2 Incorrect 664 ms 112860 KB Output isn't correct
3 Incorrect 1183 ms 116724 KB Output isn't correct
4 Correct 165 ms 116344 KB Output is correct
5 Correct 213 ms 118860 KB Output is correct
6 Incorrect 332 ms 122156 KB Output isn't correct
7 Correct 629 ms 124760 KB Output is correct
8 Incorrect 554 ms 129992 KB Output isn't correct
9 Runtime error 103 ms 131072 KB Execution killed with signal 9
10 Runtime error 104 ms 131072 KB Execution killed with signal 9
11 Runtime error 124 ms 131072 KB Execution killed with signal 9
12 Runtime error 128 ms 131072 KB Execution killed with signal 9
13 Runtime error 113 ms 131072 KB Execution killed with signal 9
14 Runtime error 133 ms 131072 KB Execution killed with signal 9
15 Runtime error 71 ms 131072 KB Execution killed with signal 9
16 Runtime error 79 ms 131072 KB Execution killed with signal 9
17 Runtime error 72 ms 131072 KB Execution killed with signal 9