oj.uz

Submission #763785

# Submission time Handle Problem Language Result Execution time Memory
763785 2023-06-22T21:06:09 Z izanbf Regions (IOI09_regions) C++14
100 / 100
 5836 ms 110480 KB 
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

const int BIG = 300;
vi r, tin, tout, big_id;
vvi adj, tins, touts, by_r;
int dp[250'000/BIG+1][250'000];
int timer;

void euler(int u, int p) {
    tin[u] = timer++;
    tins[r[u]].push_back(tin[u]);
    for (int v : adj[u]) {
        if (v != p) euler(v, u);
    }
    tout[u] = timer++;
    touts[r[u]].push_back(tout[u]);
}

int count_in_range(const vi& v, int l, int r) {
    if (v.empty()) return 0;
    int ri = upper_bound(v.begin(), v.end(), r) - v.begin();
    int li = upper_bound(v.begin(), v.end(), l) - v.begin();
    return ri - li;
}

void precompute(int rg, int p, int u) {
    int rid = big_id[rg];
    dp[rid][u] = (r[u] == rg);
    for (int v : adj[u]) {
        if (v != p) {
            precompute(rg, u, v);
            dp[rid][u] += dp[rid][v];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N, R, Q;
    cin >> N >> R >> Q;

    r = tin = tout = vi(N);
    big_id = vi(R);
    adj = vvi(N);
    tins = touts = by_r = vvi(R);

    vi p(N, -1);

    cin >> r[0]; --r[0];
    by_r[r[0]].push_back(0);

    for (int i = 1; i < N; ++i) {
        cin >> p[i] >> r[i]; --p[i], --r[i];
        by_r[r[i]].push_back(i);
        adj[i].push_back(p[i]);
        adj[p[i]].push_back(i);
    }

    int bigs = 0;
    for (int rg = 0; rg < R; ++rg) {
        if (by_r[rg].size() >= BIG) big_id[rg] = bigs++;
    }

    for (int rg = 0; rg < R; ++rg) { // O(N/BIG N)
        if (by_r[rg].size() >= BIG) precompute(rg, 0, 0);
    }

    timer = 1;
    euler(0, 0);

    map<pair<int,int>,long long> mem;

    while (Q--) {
        int r1, r2;
        cin >> r1 >> r2; --r1, --r2;
        if (by_r[r1].size() < BIG and by_r[r2].size() >= BIG) { // r1 small r2 big  O(Q BIG)
            long long cnt = 0;
            int rid = big_id[r2];
            for (int u : by_r[r1]) {
                cnt += dp[rid][u];
            }
            cout << cnt << endl;
        }
        else { //O(Q BIG log N)
            if (not mem.count({r1,r2})) {
                long long cnt = 0;
                for (int u : by_r[r2]) {
                    cnt += count_in_range(tins[r1], 0, tin[u])
                         - count_in_range(touts[r1], 0, tin[u]);
                }
                mem[{r1,r2}] = cnt;
            }
            cout << mem[{r1,r2}] << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 18 ms 524 KB Output is correct
7 Correct 16 ms 624 KB Output is correct
8 Correct 32 ms 664 KB Output is correct
9 Correct 48 ms 1388 KB Output is correct
10 Correct 75 ms 1744 KB Output is correct
11 Correct 113 ms 2264 KB Output is correct
12 Correct 137 ms 3160 KB Output is correct
13 Correct 144 ms 3260 KB Output is correct
14 Correct 213 ms 3972 KB Output is correct
15 Correct 293 ms 7408 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1096 ms 16384 KB Output is correct
2 Correct 1431 ms 13220 KB Output is correct
3 Correct 1825 ms 18256 KB Output is correct
4 Correct 280 ms 5088 KB Output is correct
5 Correct 358 ms 7756 KB Output is correct
6 Correct 520 ms 20504 KB Output is correct
7 Correct 868 ms 23228 KB Output is correct
8 Correct 1102 ms 58072 KB Output is correct
9 Correct 2004 ms 54748 KB Output is correct
10 Correct 3498 ms 99988 KB Output is correct
11 Correct 5836 ms 110480 KB Output is correct
12 Correct 1412 ms 23968 KB Output is correct
13 Correct 1963 ms 27184 KB Output is correct
14 Correct 2732 ms 44324 KB Output is correct
15 Correct 3722 ms 37332 KB Output is correct
16 Correct 3240 ms 46284 KB Output is correct
17 Correct 3084 ms 59980 KB Output is correct