oj.uz

Submission #939714

# Submission time Handle Problem Language Result Execution time Memory
939714 2024-03-06T16:55:52 Z ifateen Regions (IOI09_regions) C++14
100 / 100
 5301 ms 45168 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
const int MAXN = 2e5 + 5, MAXSQRT = 501;
vector<int> adj[MAXN], comp[MAXN], region_in_times[MAXN];
int cmp[MAXN], in_time[MAXN], sub[MAXN], ans[MAXSQRT][25005], processed_index[MAXN], timer = 0;

void dfs(int u) {
    sub[u] = 1;
    in_time[u] = ++timer;
    region_in_times[cmp[u]].push_back(in_time[u]);
    for (auto &v: adj[u]) {
        dfs(v);
        sub[u] += sub[v];
    }
}

void pre_process(int u, int idx, int cnt) {
    if (cmp[u] == idx) cnt++;
    ans[processed_index[idx]][cmp[u]] += cnt;
    for (auto &v: adj[u]) pre_process(v, idx, cnt);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, r, q;
    cin >> n >> r >> q;
    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            int par;
            cin >> par;
            adj[par].push_back(i);
        }
        cin >> cmp[i];
        comp[cmp[i]].push_back(i);
    }
    dfs(1);
    timer = 0;
    int cnt = 0;
    for (int i = 1; i <= r; i++) {
        if (comp[i].size() <= MAXSQRT) continue;
        processed_index[i] = ++cnt;
        pre_process(1, i, 0);
    }
    while (q--) {
        int a, b;
        cin >> a >> b;
        if (processed_index[a]) cout << ans[processed_index[a]][b] << endl;
        else {
            int ret = 0;
            for (auto &u: comp[a])
                ret += lower_bound(all(region_in_times[b]), in_time[u] + sub[u]) -
                       lower_bound(all(region_in_times[b]), in_time[u]);
            cout << ret << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20308 KB Output is correct
2 Correct 4 ms 20056 KB Output is correct
3 Correct 6 ms 20056 KB Output is correct
4 Correct 6 ms 20056 KB Output is correct
5 Correct 8 ms 20056 KB Output is correct
6 Correct 13 ms 20056 KB Output is correct
7 Correct 20 ms 20056 KB Output is correct
8 Correct 18 ms 20312 KB Output is correct
9 Correct 26 ms 20644 KB Output is correct
10 Correct 50 ms 20568 KB Output is correct
11 Correct 74 ms 20824 KB Output is correct
12 Correct 96 ms 21316 KB Output is correct
13 Correct 125 ms 21080 KB Output is correct
14 Correct 224 ms 21888 KB Output is correct
15 Correct 206 ms 24380 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1572 ms 28824 KB Output is correct
2 Correct 1907 ms 27820 KB Output is correct
3 Correct 2427 ms 30572 KB Output is correct
4 Correct 180 ms 21900 KB Output is correct
5 Correct 258 ms 23668 KB Output is correct
6 Correct 1211 ms 22964 KB Output is correct
7 Correct 1417 ms 23872 KB Output is correct
8 Correct 986 ms 28852 KB Output is correct
9 Correct 2099 ms 29764 KB Output is correct
10 Correct 4522 ms 34280 KB Output is correct
11 Correct 5301 ms 29476 KB Output is correct
12 Correct 1243 ms 32432 KB Output is correct
13 Correct 1621 ms 32720 KB Output is correct
14 Correct 1597 ms 36904 KB Output is correct
15 Correct 2390 ms 36552 KB Output is correct
16 Correct 2130 ms 41568 KB Output is correct
17 Correct 2117 ms 45168 KB Output is correct