oj.uz

Submission #569748

# Submission time Handle Problem Language Result Execution time Memory
569748 2022-05-27T17:30:28 Z erto Regions (IOI09_regions) C++17
90 / 100
 8000 ms 62456 KB 
#include <bits/stdc++.h>
typedef long long int ll;
#define INF (1e9 + 7)
#define INF2 (998244353)
#define N (ll)2e5 + 5
using namespace std;
//#define int ll

int n, g, h, t1, t2, cur = 1, q, R;

int d[N], st[N], en[N], par[N][20], r[N];

vector<int> v[N], sts[N], ens[N], r2[N];

void dfs(int x, int p){
    st[x] = cur++;
    sts[r[x]].push_back(cur - 1);
    r2[r[x]].push_back(x);

    par[x][0] = p;
    for(int i = 1; i<=20; i++){
        par[x][i] = par[par[x][i - 1]][i - 1];
    }

    for(auto u : v[x]){
        if(u != p)dfs(u, x);
    }
    en[x] = cur++;
    ens[r[x]].push_back(cur - 1);
}

void solve(){
    cin >> n >> R >> q;
    cin >> r[1];

    for(int i=2; i<=n; i++){
        cin >> g >> r[i];
        v[g].push_back(i);
    }
    dfs(1, 0);

    for(int i=1; i<=q; i++){
        cin >> g >> h;
        if(sts[g].size() > sts[h].size()){
            int sum=0;
            for(auto u : r2[h]){
                t1 = lower_bound(sts[g].begin(), sts[g].end(), st[u]) - sts[g].begin();
                t2 = lower_bound(ens[g].begin(), ens[g].end(), st[u]) - ens[g].begin();
                sum += t1 - t2;
            }
            cout << sum << endl;
        }
        else{
            int sum=0;
            for(auto u : r2[g]){
                t1 = lower_bound(ens[h].begin(), ens[h].end(), st[u]) - ens[h].begin();
                t2 = lower_bound(ens[h].begin(), ens[h].end(), en[u]) - ens[h].begin();
                sum += t2 - t1;
            }
            cout << sum << endl;
        }
    }
}   



signed main(){ 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    while (T--){
        solve();
    }
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:22:19: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   22 |         par[x][i] = par[par[x][i - 1]][i - 1];
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:21:21: note: within this loop
   21 |     for(int i = 1; i<=20; i++){
      |                    ~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19024 KB Output is correct
2 Correct 10 ms 19024 KB Output is correct
3 Correct 11 ms 19024 KB Output is correct
4 Correct 15 ms 19024 KB Output is correct
5 Correct 16 ms 19152 KB Output is correct
6 Correct 26 ms 19220 KB Output is correct
7 Correct 34 ms 19280 KB Output is correct
8 Correct 41 ms 19408 KB Output is correct
9 Correct 54 ms 20184 KB Output is correct
10 Correct 87 ms 20432 KB Output is correct
11 Correct 125 ms 21200 KB Output is correct
12 Correct 152 ms 22296 KB Output is correct
13 Correct 140 ms 22096 KB Output is correct
14 Correct 247 ms 23312 KB Output is correct
15 Correct 232 ms 27916 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 7976 ms 30492 KB Output is correct
2 Execution timed out 8054 ms 29360 KB Time limit exceeded
3 Execution timed out 8035 ms 34128 KB Time limit exceeded
4 Correct 239 ms 23504 KB Output is correct
5 Correct 404 ms 26224 KB Output is correct
6 Correct 1022 ms 26668 KB Output is correct
7 Correct 1381 ms 29304 KB Output is correct
8 Correct 1121 ms 38736 KB Output is correct
9 Correct 2086 ms 42164 KB Output is correct
10 Correct 3716 ms 50976 KB Output is correct
11 Correct 3858 ms 45828 KB Output is correct
12 Correct 1451 ms 45996 KB Output is correct
13 Correct 1874 ms 46668 KB Output is correct
14 Correct 2338 ms 47148 KB Output is correct
15 Correct 2800 ms 53704 KB Output is correct
16 Correct 2938 ms 62456 KB Output is correct
17 Correct 6509 ms 60468 KB Output is correct