oj.uz

Submission #763771

# Submission time Handle Problem Language Result Execution time Memory
763771 2023-06-22T20:41:18 Z izanbf Regions (IOI09_regions) C++14
100 / 100
 6688 ms 57880 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int BIG = 4000;
vi r, tin, tout, big_id;
vvi adj, tins, touts, by_r;
vector<vector<long long>> 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 i = upper_bound(v.begin(), v.end(), r) - v.begin();
    int j = upper_bound(v.begin(), v.end(), l) - v.begin();
    // cerr << "$$" << 1+rg << " " << l << " " << r << " " << j << " " << i << " " << i - j << endl;
    return i - j;
}

void precompute(int rg, int p, int u) {
    // cerr << "%" << 1+rg << " " << 1+u << endl;
    int rid = big_id[rg];
    cerr << 1+rg << " RID " << rid << " " << u << endl;
    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++;
    }

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

    timer = 1;
    euler(0, 0);

    // for (int x : tins[3-1]) cerr << x << " "; cerr << endl;

    // for (int i = 0; i < N; ++i) {
    //     cerr << 1+i << " " << 1+r[i] << "  " << tin[i] << " " << tout[i] << endl;
    // }

    // for (int i = 1; i < N; ++i) {
    //     cerr << 1+i << "(" << 1+r[i] << ")" 
    //     << " " << 1+p[i] << "(" << 1+r[p[i]] << ")" << endl;
    // }
    // cerr << endl << endl;

    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 1 ms 208 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 12 ms 628 KB Output is correct
7 Correct 30 ms 528 KB Output is correct
8 Correct 25 ms 660 KB Output is correct
9 Correct 46 ms 1392 KB Output is correct
10 Correct 81 ms 1640 KB Output is correct
11 Correct 110 ms 2268 KB Output is correct
12 Correct 116 ms 3128 KB Output is correct
13 Correct 192 ms 3340 KB Output is correct
14 Correct 267 ms 3860 KB Output is correct
15 Correct 278 ms 7280 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2386 ms 14968 KB Output is correct
2 Correct 2889 ms 14684 KB Output is correct
3 Correct 3131 ms 18920 KB Output is correct
4 Correct 263 ms 5076 KB Output is correct
5 Correct 281 ms 7800 KB Output is correct
6 Correct 464 ms 8056 KB Output is correct
7 Correct 729 ms 9172 KB Output is correct
8 Correct 1226 ms 18684 KB Output is correct
9 Correct 2308 ms 25120 KB Output is correct
10 Correct 3902 ms 34164 KB Output is correct
11 Correct 4822 ms 33440 KB Output is correct
12 Correct 3615 ms 32264 KB Output is correct
13 Correct 4115 ms 35388 KB Output is correct
14 Correct 5499 ms 38024 KB Output is correct
15 Correct 5664 ms 46348 KB Output is correct
16 Correct 5545 ms 55208 KB Output is correct
17 Correct 6688 ms 57880 KB Output is correct