oj.uz

Submission #569750

# Submission time Handle Problem Language Result Execution time Memory
569750 2022-05-27T17:36:27 Z erto Regions (IOI09_regions) C++17
100 / 100
 3864 ms 80872 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];
map<int, int> m[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(m[g][h]){
            cout << m[g][h] - 1 << endl;
            continue;
        }
        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;
            }
            m[g][h] = sum + 1;
            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;
            }
            m[g][h] = sum + 1;
            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:23:19: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   23 |         par[x][i] = par[par[x][i - 1]][i - 1];
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:22:21: note: within this loop
   22 |     for(int i = 1; i<=20; i++){
      |                    ~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28496 KB Output is correct
2 Correct 15 ms 28496 KB Output is correct
3 Correct 17 ms 28468 KB Output is correct
4 Correct 18 ms 28496 KB Output is correct
5 Correct 26 ms 28536 KB Output is correct
6 Correct 37 ms 28744 KB Output is correct
7 Correct 42 ms 28768 KB Output is correct
8 Correct 43 ms 28912 KB Output is correct
9 Correct 62 ms 29776 KB Output is correct
10 Correct 99 ms 30164 KB Output is correct
11 Correct 108 ms 30948 KB Output is correct
12 Correct 156 ms 32136 KB Output is correct
13 Correct 116 ms 32060 KB Output is correct
14 Correct 260 ms 33292 KB Output is correct
15 Correct 184 ms 37960 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 959 ms 41168 KB Output is correct
2 Correct 1140 ms 40092 KB Output is correct
3 Correct 1810 ms 46600 KB Output is correct
4 Correct 193 ms 34032 KB Output is correct
5 Correct 356 ms 37440 KB Output is correct
6 Correct 376 ms 37580 KB Output is correct
7 Correct 677 ms 39788 KB Output is correct
8 Correct 920 ms 51152 KB Output is correct
9 Correct 1754 ms 57628 KB Output is correct
10 Correct 3688 ms 68016 KB Output is correct
11 Correct 3864 ms 63832 KB Output is correct
12 Correct 1468 ms 59200 KB Output is correct
13 Correct 2044 ms 61340 KB Output is correct
14 Correct 2483 ms 62812 KB Output is correct
15 Correct 3167 ms 71368 KB Output is correct
16 Correct 3089 ms 80872 KB Output is correct
17 Correct 2886 ms 78352 KB Output is correct