oj.uz

Submission #763767

# Submission time Handle Problem Language Result Execution time Memory
763767 2023-06-22T20:36:07 Z izanbf Regions (IOI09_regions) C++14
30 / 100
 8000 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;
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 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 388 KB Output is correct
6 Correct 17 ms 508 KB Output is correct
7 Correct 12 ms 588 KB Output is correct
8 Correct 30 ms 704 KB Output is correct
9 Correct 45 ms 1280 KB Output is correct
10 Correct 46 ms 1704 KB Output is correct
11 Correct 107 ms 2232 KB Output is correct
12 Correct 94 ms 3040 KB Output is correct
13 Correct 128 ms 3340 KB Output is correct
14 Correct 274 ms 3804 KB Output is correct
15 Correct 477 ms 9044 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8018 ms 87616 KB Time limit exceeded
2 Execution timed out 8067 ms 129748 KB Time limit exceeded
3 Runtime error 58 ms 131072 KB Execution killed with signal 9
4 Correct 251 ms 5116 KB Output is correct
5 Correct 294 ms 7764 KB Output is correct
6 Execution timed out 8037 ms 53708 KB Time limit exceeded
7 Execution timed out 8007 ms 63112 KB Time limit exceeded
8 Execution timed out 8069 ms 114924 KB Time limit exceeded
9 Runtime error 70 ms 131072 KB Execution killed with signal 9
10 Runtime error 75 ms 131072 KB Execution killed with signal 9
11 Runtime error 90 ms 131072 KB Execution killed with signal 9
12 Runtime error 79 ms 131072 KB Execution killed with signal 9
13 Runtime error 83 ms 131072 KB Execution killed with signal 9
14 Execution timed out 8058 ms 91100 KB Time limit exceeded
15 Correct 5598 ms 46344 KB Output is correct
16 Runtime error 103 ms 131072 KB Execution killed with signal 9
17 Execution timed out 8064 ms 105296 KB Time limit exceeded