oj.uz

Submission #763780

# Submission time Handle Problem Language Result Execution time Memory
763780 2023-06-22T20:59:45 Z izanbf Regions (IOI09_regions) C++14
100 / 100
 5290 ms 110460 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int BIG = 300;
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 3 ms 208 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 19 ms 464 KB Output is correct
7 Correct 29 ms 560 KB Output is correct
8 Correct 33 ms 636 KB Output is correct
9 Correct 32 ms 1416 KB Output is correct
10 Correct 81 ms 1712 KB Output is correct
11 Correct 101 ms 2232 KB Output is correct
12 Correct 143 ms 3076 KB Output is correct
13 Correct 165 ms 3240 KB Output is correct
14 Correct 241 ms 3900 KB Output is correct
15 Correct 205 ms 7408 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1088 ms 16320 KB Output is correct
2 Correct 1388 ms 13272 KB Output is correct
3 Correct 1760 ms 18288 KB Output is correct
4 Correct 259 ms 5376 KB Output is correct
5 Correct 358 ms 7764 KB Output is correct
6 Correct 579 ms 20140 KB Output is correct
7 Correct 695 ms 23136 KB Output is correct
8 Correct 1016 ms 57832 KB Output is correct
9 Correct 2228 ms 54572 KB Output is correct
10 Correct 3534 ms 100000 KB Output is correct
11 Correct 5290 ms 110460 KB Output is correct
12 Correct 1398 ms 24092 KB Output is correct
13 Correct 1978 ms 27208 KB Output is correct
14 Correct 2340 ms 44416 KB Output is correct
15 Correct 3003 ms 37356 KB Output is correct
16 Correct 2901 ms 46340 KB Output is correct
17 Correct 2813 ms 60012 KB Output is correct