oj.uz

Submission #763792

# Submission time Handle Problem Language Result Execution time Memory
763792 2023-06-22T21:10:41 Z izanbf Regions (IOI09_regions) C++14
100 / 100
 4959 ms 46216 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, 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 1 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 19 ms 504 KB Output is correct
7 Correct 13 ms 616 KB Output is correct
8 Correct 31 ms 620 KB Output is correct
9 Correct 45 ms 1316 KB Output is correct
10 Correct 66 ms 1740 KB Output is correct
11 Correct 137 ms 2368 KB Output is correct
12 Correct 138 ms 3064 KB Output is correct
13 Correct 180 ms 3360 KB Output is correct
14 Correct 296 ms 3780 KB Output is correct
15 Correct 299 ms 7388 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1170 ms 10584 KB Output is correct
2 Correct 1352 ms 10160 KB Output is correct
3 Correct 1725 ms 17124 KB Output is correct
4 Correct 298 ms 5128 KB Output is correct
5 Correct 336 ms 7700 KB Output is correct
6 Correct 563 ms 8056 KB Output is correct
7 Correct 732 ms 9244 KB Output is correct
8 Correct 1261 ms 18640 KB Output is correct
9 Correct 2467 ms 25152 KB Output is correct
10 Correct 3848 ms 34124 KB Output is correct
11 Correct 4959 ms 33412 KB Output is correct
12 Correct 1283 ms 24088 KB Output is correct
13 Correct 1836 ms 27368 KB Output is correct
14 Correct 3100 ms 29448 KB Output is correct
15 Correct 3123 ms 37464 KB Output is correct
16 Correct 3029 ms 46216 KB Output is correct
17 Correct 3270 ms 44792 KB Output is correct