oj.uz

Submission #852564

# Submission time Handle Problem Language Result Execution time Memory
852564 2023-09-22T05:41:38 Z abcvuitunggio Regions (IOI09_regions) C++17
30 / 100
 1180 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 (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
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 13 ms 107096 KB Output is correct
4 Correct 14 ms 107096 KB Output is correct
5 Correct 17 ms 107096 KB Output is correct
6 Correct 20 ms 107096 KB Output is correct
7 Correct 26 ms 107096 KB Output is correct
8 Correct 30 ms 107092 KB Output is correct
9 Correct 41 ms 107608 KB Output is correct
10 Correct 63 ms 110936 KB Output is correct
11 Correct 70 ms 110060 KB Output is correct
12 Correct 80 ms 111984 KB Output is correct
13 Correct 101 ms 110356 KB Output is correct
14 Correct 132 ms 110948 KB Output is correct
15 Correct 190 ms 114684 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 630 ms 114180 KB Output isn't correct
2 Incorrect 674 ms 112852 KB Output isn't correct
3 Incorrect 1180 ms 116532 KB Output isn't correct
4 Correct 156 ms 116344 KB Output is correct
5 Correct 217 ms 118620 KB Output is correct
6 Incorrect 329 ms 122244 KB Output isn't correct
7 Correct 630 ms 124764 KB Output is correct
8 Incorrect 620 ms 130216 KB Output isn't correct
9 Runtime error 99 ms 131072 KB Execution killed with signal 9
10 Runtime error 100 ms 131072 KB Execution killed with signal 9
11 Runtime error 135 ms 131072 KB Execution killed with signal 9
12 Runtime error 126 ms 131072 KB Execution killed with signal 9
13 Runtime error 120 ms 131072 KB Execution killed with signal 9
14 Runtime error 143 ms 131072 KB Execution killed with signal 9
15 Runtime error 67 ms 131072 KB Execution killed with signal 9
16 Runtime error 83 ms 131072 KB Execution killed with signal 9
17 Runtime error 67 ms 131072 KB Execution killed with signal 9