oj.uz

Submission #763793

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

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

const int BIG = 800;
vi r, tin, tout, big_id;
vvi adj, tins, touts, by_r, dp;
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++;
    }

    dp = vvi(bigs, vi(N)); // O(N/BIG N)
    for (int rg = 0; rg < R; ++rg) {
        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 2 ms 208 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 5 ms 408 KB Output is correct
6 Correct 19 ms 540 KB Output is correct
7 Correct 27 ms 604 KB Output is correct
8 Correct 28 ms 696 KB Output is correct
9 Correct 40 ms 1320 KB Output is correct
10 Correct 65 ms 1800 KB Output is correct
11 Correct 130 ms 2256 KB Output is correct
12 Correct 150 ms 3128 KB Output is correct
13 Correct 192 ms 3264 KB Output is correct
14 Correct 264 ms 3780 KB Output is correct
15 Correct 306 ms 7364 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 10496 KB Output is correct
2 Correct 1262 ms 12524 KB Output is correct
3 Correct 2021 ms 18204 KB Output is correct
4 Correct 284 ms 5120 KB Output is correct
5 Correct 331 ms 7784 KB Output is correct
6 Correct 547 ms 8028 KB Output is correct
7 Correct 765 ms 9216 KB Output is correct
8 Correct 1231 ms 18656 KB Output is correct
9 Correct 2399 ms 25128 KB Output is correct
10 Correct 4032 ms 34196 KB Output is correct
11 Correct 4793 ms 33308 KB Output is correct
12 Correct 1374 ms 24056 KB Output is correct
13 Correct 1745 ms 27340 KB Output is correct
14 Correct 2351 ms 39876 KB Output is correct
15 Correct 3125 ms 37540 KB Output is correct
16 Correct 3150 ms 46360 KB Output is correct
17 Correct 2791 ms 54780 KB Output is correct