oj.uz

Submission #763774

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

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

const int BIG = 100;
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 0 ms 316 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 6 ms 336 KB Output is correct
6 Correct 8 ms 544 KB Output is correct
7 Correct 19 ms 544 KB Output is correct
8 Correct 32 ms 620 KB Output is correct
9 Correct 44 ms 1388 KB Output is correct
10 Correct 69 ms 1736 KB Output is correct
11 Correct 120 ms 2268 KB Output is correct
12 Correct 140 ms 3124 KB Output is correct
13 Correct 180 ms 3292 KB Output is correct
14 Correct 443 ms 51136 KB Output is correct
15 Correct 471 ms 83964 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1771 ms 127480 KB Output is correct
2 Correct 2053 ms 111664 KB Output is correct
3 Runtime error 61 ms 131072 KB Execution killed with signal 9
4 Correct 306 ms 28336 KB Output is correct
5 Correct 405 ms 21888 KB Output is correct
6 Correct 550 ms 32468 KB Output is correct
7 Correct 1006 ms 63088 KB Output is correct
8 Runtime error 64 ms 131072 KB Execution killed with signal 9
9 Runtime error 75 ms 131072 KB Execution killed with signal 9
10 Runtime error 85 ms 131072 KB Execution killed with signal 9
11 Runtime error 93 ms 131072 KB Execution killed with signal 9
12 Runtime error 82 ms 131072 KB Execution killed with signal 9
13 Runtime error 82 ms 131072 KB Execution killed with signal 9
14 Runtime error 88 ms 131072 KB Execution killed with signal 9
15 Runtime error 87 ms 131072 KB Execution killed with signal 9
16 Runtime error 87 ms 131072 KB Execution killed with signal 9
17 Runtime error 80 ms 131072 KB Execution killed with signal 9