oj.uz

Submission #964446

# Submission time Handle Problem Language Result Execution time Memory
964446 2024-04-16T22:26:13 Z eysbutno Regions (IOI09_regions) C++17
100 / 100
 4056 ms 26812 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

template<class T> bool smax(T &a, T b) {
    return a < b ? a = b, 1 : 0;
}
template<class T> bool smin(T &a, T b) {
    return a > b ? a = b, 1 : 0;
}
void solve() {
    int n, r, q;
    cin >> n >> r >> q;
    vector<int> reg(n);
    cin >> reg[0], --reg[0];
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int p, h; cin >> p >> h;
        adj[--p].push_back(i);
        reg[i] = --h;
    }
    const int b = sqrt(n);
    vector<int> tin(n), tout(n), mp(n);
    vector<vector<int>> comp(r);
    int timer = 0;
    auto tour = [&](int u, auto&& tour) -> void {
        tin[u] = timer++, mp[tin[u]] = u;
        comp[reg[u]].push_back(tin[u]);
        for (int v : adj[u]) {
            tour(v, tour);
        }
        tout[u] = timer;
    }; tour(0, tour);
    vector<vector<int>> calc;
    vector<int> id(r, -1);
    auto dfs = [&](int u, int e1, int tot,
                   auto&& dfs) -> void {
        if (reg[u] == e1) ++tot;
        calc[id[e1]][reg[u]] += tot;
        for (int v : adj[u]) {
            dfs(v, e1, tot, dfs);
        }
    };
    int run = 0;
    for (int i = 0; i < r; i++) {
        if (sz(comp[i]) >= b) {
            id[i] = run++;
            calc.push_back(vector<int>(r));
            dfs(0, i, 0, dfs);
        }
    }
    while (q--) {
        int e1, e2;
        cin >> e1 >> e2;
        --e1, --e2;
        if (sz(comp[e1]) >= b) {
            cout << calc[id[e1]][e2] << "\n";
        } else {
            int tot = 0;
            for (int u : comp[e1]) {
                tot += lower_bound(all(comp[e2]), tout[mp[u]])
                     - lower_bound(all(comp[e2]), tin[mp[u]]);
            }
            cout << tot << "\n";
        }
    }
}
int main() {
    int t = 1; // cin >> t;
    while (t--) solve();
}
/**
 * TASK: Regions (IOI)
 * The idea: for regions with size > sqrt(N), precompute
 * the result. Otherwise, answer the queries online...
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Correct 18 ms 600 KB Output is correct
9 Correct 25 ms 856 KB Output is correct
10 Correct 60 ms 1112 KB Output is correct
11 Correct 91 ms 1592 KB Output is correct
12 Correct 93 ms 1888 KB Output is correct
13 Correct 132 ms 1912 KB Output is correct
14 Correct 213 ms 2540 KB Output is correct
15 Correct 235 ms 4672 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1637 ms 6468 KB Output is correct
2 Correct 1977 ms 5676 KB Output is correct
3 Correct 2597 ms 8244 KB Output is correct
4 Correct 201 ms 2624 KB Output is correct
5 Correct 281 ms 4140 KB Output is correct
6 Correct 410 ms 6160 KB Output is correct
7 Correct 913 ms 7940 KB Output is correct
8 Correct 764 ms 14340 KB Output is correct
9 Correct 1973 ms 12840 KB Output is correct
10 Correct 2523 ms 26812 KB Output is correct
11 Correct 4056 ms 14292 KB Output is correct
12 Correct 1194 ms 15604 KB Output is correct
13 Correct 1734 ms 15512 KB Output is correct
14 Correct 1912 ms 17372 KB Output is correct
15 Correct 2797 ms 18920 KB Output is correct
16 Correct 2643 ms 22140 KB Output is correct
17 Correct 2454 ms 22900 KB Output is correct