oj.uz

Submission #763770

# Submission time Handle Problem Language Result Execution time Memory
763770 2023-06-22T20:38:50 Z izanbf Regions (IOI09_regions) C++14
100 / 100
 7005 ms 57836 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int BIG = 2000;
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 256 KB Output is correct
2 Correct 1 ms 236 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 4 ms 428 KB Output is correct
6 Correct 17 ms 556 KB Output is correct
7 Correct 17 ms 588 KB Output is correct
8 Correct 18 ms 732 KB Output is correct
9 Correct 39 ms 1376 KB Output is correct
10 Correct 99 ms 1684 KB Output is correct
11 Correct 127 ms 2264 KB Output is correct
12 Correct 150 ms 3100 KB Output is correct
13 Correct 196 ms 3344 KB Output is correct
14 Correct 298 ms 3796 KB Output is correct
15 Correct 346 ms 7388 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2937 ms 14956 KB Output is correct
2 Correct 3282 ms 14740 KB Output is correct
3 Correct 7005 ms 29432 KB Output is correct
4 Correct 259 ms 5092 KB Output is correct
5 Correct 292 ms 7800 KB Output is correct
6 Correct 555 ms 7964 KB Output is correct
7 Correct 752 ms 9212 KB Output is correct
8 Correct 1259 ms 18840 KB Output is correct
9 Correct 2611 ms 25232 KB Output is correct
10 Correct 4328 ms 34076 KB Output is correct
11 Correct 4715 ms 33292 KB Output is correct
12 Correct 3698 ms 32404 KB Output is correct
13 Correct 4207 ms 35216 KB Output is correct
14 Correct 5396 ms 38036 KB Output is correct
15 Correct 5451 ms 46384 KB Output is correct
16 Correct 5358 ms 55476 KB Output is correct
17 Correct 6470 ms 57836 KB Output is correct