oj.uz

Submission #976649

# Submission time Handle Problem Language Result Execution time Memory
976649 2024-05-07T00:13:49 Z eysbutno Regions (IOI09_regions) C++17
100 / 100
 3804 ms 34676 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, r, q;
    cin >> n >> r >> q;
    vector<int> region(n);
    cin >> region[0];
    --region[0];
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int p, h; 
        cin >> p >> h;
        --p, --h;
        adj[p].push_back(i);
        region[i] = h;
    }
    // Calculating Euler tour indices.
    vector<int> tin(n), tout(n), mp(n);
    vector<vector<int>> comp(r);
    int timer = 0;
    function<void(int)> tour = [&](int u) -> void {
        tin[u] = timer++;
        mp[tin[u]] = u;
        comp[region[u]].push_back(tin[u]);
        for (int v : adj[u]) {
            tour(v);
        }
        tout[u] = timer;
    }; 
    tour(0);
    // Precalculating the answer for parent regions with
    // >= sqrt(n) members.
    const int BLOCK = sqrt(n);
    vector<vector<int>> calc;
    vector<int> region_id(r, -1);
    function<void(int, int, int)> dfs = [&](int u, int parent_region, 
                                            int parent_count) -> void {
        if (region[u] == parent_region) ++parent_count;
        calc[region_id[parent_region]][region[u]] += parent_count;
        for (int v : adj[u]) {
            dfs(v, parent_region, parent_count);
        }
    };
    int current_id = 0;
    for (int i = 0; i < r; i++) {
        if ((int) comp[i].size() >= BLOCK) {
            region_id[i] = current_id++;
            calc.push_back(vector<int>(r));
            dfs(0, i, 0);
        }
    }
    // Answering the queries, either with the precalculated
    // values or by using Euler tour + binary search.
    while (q--) {
        int e1, e2;
        cin >> e1 >> e2;
        --e1, --e2;
        if ((int) comp[e1].size() >= BLOCK) {
            cout << calc[region_id[e1]][e2] << "\n";
        } else {
            int tot = 0;
            for (int u : comp[e1]) {
                tot += lower_bound(begin(comp[e2]), end(comp[e2]), tout[mp[u]])
                     - lower_bound(begin(comp[e2]), end(comp[e2]), tin[mp[u]]);
            }
            cout << tot << "\n";
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Correct 25 ms 600 KB Output is correct
9 Correct 29 ms 1112 KB Output is correct
10 Correct 50 ms 1364 KB Output is correct
11 Correct 81 ms 1488 KB Output is correct
12 Correct 92 ms 2200 KB Output is correct
13 Correct 126 ms 1952 KB Output is correct
14 Correct 203 ms 2460 KB Output is correct
15 Correct 224 ms 7304 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1534 ms 7444 KB Output is correct
2 Correct 1763 ms 5796 KB Output is correct
3 Correct 2452 ms 10552 KB Output is correct
4 Correct 197 ms 2592 KB Output is correct
5 Correct 256 ms 5024 KB Output is correct
6 Correct 403 ms 6632 KB Output is correct
7 Correct 870 ms 8256 KB Output is correct
8 Correct 859 ms 18800 KB Output is correct
9 Correct 1827 ms 13668 KB Output is correct
10 Correct 2546 ms 32744 KB Output is correct
11 Correct 3804 ms 14404 KB Output is correct
12 Correct 1156 ms 15828 KB Output is correct
13 Correct 1540 ms 16772 KB Output is correct
14 Correct 1824 ms 17928 KB Output is correct
15 Correct 2592 ms 23496 KB Output is correct
16 Correct 2396 ms 34676 KB Output is correct
17 Correct 2441 ms 33820 KB Output is correct