oj.uz

Submission #763781

# Submission time Handle Problem Language Result Execution time Memory
763781 2023-06-22T21:01:18 Z izanbf Regions (IOI09_regions) C++14
95 / 100
 3293 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int BIG = 250;
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 0 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 14 ms 484 KB Output is correct
7 Correct 26 ms 696 KB Output is correct
8 Correct 33 ms 1028 KB Output is correct
9 Correct 39 ms 1304 KB Output is correct
10 Correct 72 ms 1740 KB Output is correct
11 Correct 114 ms 2252 KB Output is correct
12 Correct 122 ms 3224 KB Output is correct
13 Correct 193 ms 3352 KB Output is correct
14 Correct 276 ms 3776 KB Output is correct
15 Correct 276 ms 7328 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 16120 KB Output is correct
2 Correct 1368 ms 35664 KB Output is correct
3 Correct 1893 ms 18128 KB Output is correct
4 Correct 256 ms 5088 KB Output is correct
5 Correct 371 ms 7716 KB Output is correct
6 Correct 573 ms 20092 KB Output is correct
7 Correct 827 ms 23004 KB Output is correct
8 Correct 1014 ms 57756 KB Output is correct
9 Correct 2195 ms 81416 KB Output is correct
10 Correct 3293 ms 99844 KB Output is correct
11 Runtime error 100 ms 131072 KB Execution killed with signal 9
12 Correct 1402 ms 24092 KB Output is correct
13 Correct 1778 ms 27296 KB Output is correct
14 Correct 2396 ms 44484 KB Output is correct
15 Correct 3183 ms 37392 KB Output is correct
16 Correct 2907 ms 71844 KB Output is correct
17 Correct 2816 ms 60064 KB Output is correct