oj.uz

Submission #763788

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

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

const int BIG = 1000;
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 1 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 3 ms 336 KB Output is correct
5 Correct 8 ms 408 KB Output is correct
6 Correct 12 ms 572 KB Output is correct
7 Correct 29 ms 632 KB Output is correct
8 Correct 33 ms 660 KB Output is correct
9 Correct 43 ms 1312 KB Output is correct
10 Correct 64 ms 1708 KB Output is correct
11 Correct 152 ms 2252 KB Output is correct
12 Correct 110 ms 3044 KB Output is correct
13 Correct 186 ms 3296 KB Output is correct
14 Correct 264 ms 3856 KB Output is correct
15 Correct 251 ms 7392 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1113 ms 10464 KB Output is correct
2 Correct 1349 ms 11760 KB Output is correct
3 Correct 1977 ms 18184 KB Output is correct
4 Correct 313 ms 5112 KB Output is correct
5 Correct 371 ms 7716 KB Output is correct
6 Correct 462 ms 7988 KB Output is correct
7 Correct 821 ms 9104 KB Output is correct
8 Correct 1186 ms 18528 KB Output is correct
9 Correct 2503 ms 25132 KB Output is correct
10 Correct 4033 ms 34128 KB Output is correct
11 Correct 4382 ms 33584 KB Output is correct
12 Correct 1358 ms 24224 KB Output is correct
13 Correct 1847 ms 27064 KB Output is correct
14 Correct 2556 ms 37820 KB Output is correct
15 Correct 3068 ms 37580 KB Output is correct
16 Correct 2934 ms 46276 KB Output is correct
17 Correct 2898 ms 53160 KB Output is correct