oj.uz

Submission #852547

# Submission time Handle Problem Language Result Execution time Memory
852547 2023-09-22T04:55:32 Z abcvuitunggio Regions (IOI09_regions) C++17
5 / 100
 7674 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=58;
int n,R,q,r1,r2,cnt[200001][sz+1],c[25001][sz+1],c2[25001][sz+2],r[200001],p[200001],tin[200001],tout[200001],t;
vector <int> ke[200001],ve[25001];
void dfs(int u){
    tin[u]=++t;
    ve[r[u]].push_back(t);
    if (r[u]<=sz)
        cnt[u][r[u]]++;
    for (int v:ke[u]){
        for (int i=1;i<=sz;i++)
            cnt[v][i]+=cnt[u][i];
        dfs(v);
    }
    for (int i=1;i<=sz;i++)
        c[r[u]][i]+=cnt[u][i];
    tout[u]=++t;
    ve[r[u]].push_back(-t);
}
void dfs2(int u){
    if (r[u]<=sz)
        cnt[u][r[u]]++;
    for (int v:ke[u]){
        dfs2(v);
        for (int i=1;i<=sz;i++)
            cnt[v][i]+=cnt[u][i];
    }
    for (int i=1;i<=sz;i++)
        c2[r[u]][i]+=cnt[u][i];
    tout[u]=++t;
    ve[r[u]].push_back(-t);
}
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];
    }
    dfs(1);
    memset(cnt,0,sizeof(cnt));
    dfs2(1);
    while (q--){
        cin >> r1 >> r2;
        if (r1<=sz){
            cout << c[r2][r1] << endl;
            continue;
        }
        if (r2<=sz){
            cout << c2[r1][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:59: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]
   59 |         for (int i=0;i<ve[r2].size();i++){
      |                      ~^~~~~~~~~~~~~~
regions.cpp:60: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]
   60 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 109144 KB Output is correct
2 Correct 13 ms 109144 KB Output is correct
3 Correct 14 ms 109144 KB Output is correct
4 Correct 15 ms 109144 KB Output is correct
5 Correct 16 ms 109144 KB Output is correct
6 Incorrect 20 ms 107352 KB Output isn't correct
7 Incorrect 26 ms 109144 KB Output isn't correct
8 Incorrect 34 ms 107352 KB Output isn't correct
9 Incorrect 40 ms 107864 KB Output isn't correct
10 Incorrect 59 ms 109712 KB Output isn't correct
11 Incorrect 79 ms 108476 KB Output isn't correct
12 Incorrect 99 ms 109156 KB Output isn't correct
13 Incorrect 120 ms 108636 KB Output isn't correct
14 Incorrect 149 ms 109200 KB Output isn't correct
15 Incorrect 181 ms 113336 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 4257 ms 113440 KB Output isn't correct
2 Incorrect 7153 ms 111784 KB Output isn't correct
3 Incorrect 7674 ms 116232 KB Output isn't correct
4 Incorrect 203 ms 113404 KB Output isn't correct
5 Incorrect 217 ms 116248 KB Output isn't correct
6 Incorrect 616 ms 117184 KB Output isn't correct
7 Incorrect 862 ms 120536 KB Output isn't correct
8 Incorrect 789 ms 127904 KB Output isn't correct
9 Incorrect 1270 ms 129940 KB Output isn't correct
10 Runtime error 103 ms 131072 KB Execution killed with signal 9
11 Runtime error 118 ms 131072 KB Execution killed with signal 9
12 Runtime error 173 ms 131072 KB Execution killed with signal 9
13 Runtime error 111 ms 131072 KB Execution killed with signal 9
14 Runtime error 135 ms 131072 KB Execution killed with signal 9
15 Runtime error 72 ms 131072 KB Execution killed with signal 9
16 Runtime error 66 ms 131072 KB Execution killed with signal 9
17 Runtime error 73 ms 131072 KB Execution killed with signal 9