oj.uz

Submission #763777

# Submission time Handle Problem Language Result Execution time Memory
763777 2023-06-22T20:57:25 Z izanbf Regions (IOI09_regions) C++14
100 / 100
 4757 ms 99964 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int BIG = 400;
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 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 14 ms 564 KB Output is correct
7 Correct 28 ms 524 KB Output is correct
8 Correct 33 ms 712 KB Output is correct
9 Correct 30 ms 1432 KB Output is correct
10 Correct 98 ms 1708 KB Output is correct
11 Correct 137 ms 2248 KB Output is correct
12 Correct 147 ms 3204 KB Output is correct
13 Correct 196 ms 3256 KB Output is correct
14 Correct 292 ms 3788 KB Output is correct
15 Correct 290 ms 7348 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1087 ms 15092 KB Output is correct
2 Correct 1287 ms 13196 KB Output is correct
3 Correct 1972 ms 18240 KB Output is correct
4 Correct 272 ms 5152 KB Output is correct
5 Correct 292 ms 7832 KB Output is correct
6 Correct 484 ms 20288 KB Output is correct
7 Correct 809 ms 16836 KB Output is correct
8 Correct 1121 ms 57704 KB Output is correct
9 Correct 2231 ms 25132 KB Output is correct
10 Correct 3551 ms 99964 KB Output is correct
11 Correct 4757 ms 33376 KB Output is correct
12 Correct 1344 ms 24088 KB Output is correct
13 Correct 1878 ms 27172 KB Output is correct
14 Correct 2273 ms 44464 KB Output is correct
15 Correct 3024 ms 37352 KB Output is correct
16 Correct 3257 ms 46360 KB Output is correct
17 Correct 3141 ms 60008 KB Output is correct