oj.uz

Submission #763776

# Submission time Handle Problem Language Result Execution time Memory
763776 2023-06-22T20:48:03 Z izanbf Regions (IOI09_regions) C++14
100 / 100
 4590 ms 54576 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;
        // cerr << 1+r1 << " " << 1+r2 << endl;
        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 0 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 6 ms 336 KB Output is correct
6 Correct 22 ms 492 KB Output is correct
7 Correct 26 ms 528 KB Output is correct
8 Correct 26 ms 892 KB Output is correct
9 Correct 43 ms 1336 KB Output is correct
10 Correct 78 ms 1740 KB Output is correct
11 Correct 160 ms 2228 KB Output is correct
12 Correct 138 ms 3372 KB Output is correct
13 Correct 208 ms 3344 KB Output is correct
14 Correct 256 ms 4140 KB Output is correct
15 Correct 300 ms 7388 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1151 ms 10480 KB Output is correct
2 Correct 1351 ms 12476 KB Output is correct
3 Correct 2051 ms 18164 KB Output is correct
4 Correct 282 ms 5180 KB Output is correct
5 Correct 347 ms 7704 KB Output is correct
6 Correct 447 ms 8048 KB Output is correct
7 Correct 683 ms 9416 KB Output is correct
8 Correct 1246 ms 18636 KB Output is correct
9 Correct 2447 ms 25008 KB Output is correct
10 Correct 4107 ms 34240 KB Output is correct
11 Correct 4590 ms 33440 KB Output is correct
12 Correct 1489 ms 24228 KB Output is correct
13 Correct 2045 ms 27112 KB Output is correct
14 Correct 2747 ms 39864 KB Output is correct
15 Correct 2975 ms 37444 KB Output is correct
16 Correct 3165 ms 46124 KB Output is correct
17 Correct 3014 ms 54576 KB Output is correct