oj.uz

Submission #763778

# Submission time Handle Problem Language Result Execution time Memory
763778 2023-06-22T20:58:35 Z izanbf Regions (IOI09_regions) C++14
75 / 100
 3132 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int BIG = 200;
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 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 4 ms 336 KB Output is correct
5 Correct 8 ms 380 KB Output is correct
6 Correct 18 ms 484 KB Output is correct
7 Correct 26 ms 580 KB Output is correct
8 Correct 23 ms 676 KB Output is correct
9 Correct 36 ms 1296 KB Output is correct
10 Correct 59 ms 1724 KB Output is correct
11 Correct 127 ms 2252 KB Output is correct
12 Correct 127 ms 3128 KB Output is correct
13 Correct 148 ms 3320 KB Output is correct
14 Correct 231 ms 3860 KB Output is correct
15 Correct 241 ms 8288 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1325 ms 39180 KB Output is correct
2 Correct 1926 ms 60908 KB Output is correct
3 Correct 2482 ms 106412 KB Output is correct
4 Correct 288 ms 5080 KB Output is correct
5 Correct 356 ms 7772 KB Output is correct
6 Correct 536 ms 20204 KB Output is correct
7 Correct 961 ms 25720 KB Output is correct
8 Correct 1091 ms 57792 KB Output is correct
9 Correct 2579 ms 81472 KB Output is correct
10 Runtime error 73 ms 131072 KB Execution killed with signal 9
11 Runtime error 120 ms 131072 KB Execution killed with signal 9
12 Runtime error 80 ms 131072 KB Execution killed with signal 9
13 Runtime error 82 ms 131072 KB Execution killed with signal 9
14 Correct 2613 ms 52172 KB Output is correct
15 Correct 3132 ms 37356 KB Output is correct
16 Runtime error 89 ms 131072 KB Execution killed with signal 9
17 Correct 2992 ms 67836 KB Output is correct