oj.uz

Submission #763773

# Submission time Handle Problem Language Result Execution time Memory
763773 2023-06-22T20:42:46 Z izanbf Regions (IOI09_regions) C++14
95 / 100
 4770 ms 131072 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;
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 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 8 ms 388 KB Output is correct
6 Correct 19 ms 516 KB Output is correct
7 Correct 27 ms 592 KB Output is correct
8 Correct 26 ms 652 KB Output is correct
9 Correct 38 ms 1316 KB Output is correct
10 Correct 49 ms 1736 KB Output is correct
11 Correct 112 ms 2228 KB Output is correct
12 Correct 135 ms 3016 KB Output is correct
13 Correct 194 ms 3460 KB Output is correct
14 Correct 289 ms 3848 KB Output is correct
15 Correct 309 ms 7392 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1221 ms 20660 KB Output is correct
2 Correct 1491 ms 17364 KB Output is correct
3 Correct 1843 ms 21728 KB Output is correct
4 Correct 247 ms 5084 KB Output is correct
5 Correct 296 ms 7808 KB Output is correct
6 Correct 570 ms 32348 KB Output is correct
7 Correct 760 ms 24112 KB Output is correct
8 Correct 1048 ms 96956 KB Output is correct
9 Correct 2528 ms 25128 KB Output is correct
10 Runtime error 77 ms 131072 KB Execution killed with signal 9
11 Correct 4770 ms 33616 KB Output is correct
12 Correct 1349 ms 25536 KB Output is correct
13 Correct 2032 ms 28700 KB Output is correct
14 Correct 2427 ms 61560 KB Output is correct
15 Correct 3234 ms 38960 KB Output is correct
16 Correct 2628 ms 47684 KB Output is correct
17 Correct 2806 ms 77956 KB Output is correct