oj.uz

Submission #574169

# Submission time Handle Problem Language Result Execution time Memory
574169 2022-06-08T05:40:11 Z RandomLB Regions (IOI09_regions) C++17
100 / 100
 4591 ms 35548 KB 
#include <bits/stdc++.h>
using namespace std;
#define siz(x) (int)x.size()
#define pb push_back
#define all(x) x.begin(), x.end()
//===========================================
const int MAX = 2e5+5;
const int BLOCK = 500;
vector<int> adj[MAX], comp[MAX], occ[MAX];
int cmp[MAX], in[MAX], sub[MAX], res[400][25005], pp[MAX], curr;

int dfs(int v){
    in[v] = ++curr;
    occ[cmp[v]].pb(in[v]);
    for (int u: adj[v]) sub[v] += dfs(u);
    return (sub[v] += 1);
}

void dfs2(int v, int tar, int curr){
    if (cmp[v] == tar) curr++;
    res[pp[tar]][cmp[v]] += curr;
    for (int u: adj[v]) dfs2(u, tar, curr);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, r, q; cin >> n >> r >> q;
    for (int i = 1; i <= n; i++){
        if (i > 1){
            int a; cin >> a;
            adj[a].pb(i);
        }
        cin >> cmp[i];
        comp[cmp[i]].pb(i);
    }
    dfs(1);
    curr = 0;
    for (int i = 1; i <= r; i++){
        if (siz(comp[i]) < BLOCK) continue;
        pp[i] = ++curr;
        dfs2(1, i, 0);
    }
    while (q--){
        int a, b; cin >> a >> b;
        if (pp[a]) cout << res[pp[a]][b] << endl;
        else {
            int tot = 0;
            for (int v: comp[a])
                tot += lower_bound(all(occ[b]), in[v]+sub[v])-lower_bound(all(occ[b]), in[v]);
            cout << tot << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14416 KB Output is correct
2 Correct 9 ms 14416 KB Output is correct
3 Correct 10 ms 14416 KB Output is correct
4 Correct 12 ms 14416 KB Output is correct
5 Correct 13 ms 14368 KB Output is correct
6 Correct 25 ms 14416 KB Output is correct
7 Correct 36 ms 14416 KB Output is correct
8 Correct 44 ms 14544 KB Output is correct
9 Correct 54 ms 14952 KB Output is correct
10 Correct 100 ms 14876 KB Output is correct
11 Correct 128 ms 15196 KB Output is correct
12 Correct 151 ms 15768 KB Output is correct
13 Correct 183 ms 15360 KB Output is correct
14 Correct 311 ms 15928 KB Output is correct
15 Correct 282 ms 18512 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1853 ms 19116 KB Output is correct
2 Correct 2142 ms 17964 KB Output is correct
3 Correct 3033 ms 20848 KB Output is correct
4 Correct 192 ms 16080 KB Output is correct
5 Correct 330 ms 17728 KB Output is correct
6 Correct 1166 ms 17888 KB Output is correct
7 Correct 1924 ms 18376 KB Output is correct
8 Correct 1298 ms 23460 KB Output is correct
9 Correct 2095 ms 23844 KB Output is correct
10 Correct 3752 ms 28744 KB Output is correct
11 Correct 4591 ms 23708 KB Output is correct
12 Correct 1453 ms 25284 KB Output is correct
13 Correct 1848 ms 25440 KB Output is correct
14 Correct 2410 ms 27068 KB Output is correct
15 Correct 2963 ms 29720 KB Output is correct
16 Correct 2901 ms 34980 KB Output is correct
17 Correct 2945 ms 35548 KB Output is correct