oj.uz

Submission #763766

# Submission time Handle Problem Language Result Execution time Memory
763766 2023-06-22T20:34:42 Z izanbf Regions (IOI09_regions) C++14
13 / 100
 8000 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
13.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 336 KB Output is correct
4 Correct 5 ms 352 KB Output is correct
5 Correct 7 ms 396 KB Output is correct
6 Correct 18 ms 584 KB Output is correct
7 Correct 28 ms 544 KB Output is correct
8 Correct 26 ms 688 KB Output is correct
9 Correct 46 ms 1292 KB Output is correct
10 Correct 82 ms 1644 KB Output is correct
11 Correct 100 ms 2260 KB Output is correct
12 Correct 162 ms 3084 KB Output is correct
13 Correct 220 ms 3240 KB Output is correct
14 Execution timed out 8060 ms 71248 KB Time limit exceeded
15 Execution timed out 8100 ms 103728 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8015 ms 131072 KB Time limit exceeded
2 Execution timed out 8015 ms 129628 KB Time limit exceeded
3 Runtime error 61 ms 131072 KB Execution killed with signal 9
4 Execution timed out 8087 ms 50396 KB Time limit exceeded
5 Execution timed out 8077 ms 42712 KB Time limit exceeded
6 Execution timed out 8061 ms 53540 KB Time limit exceeded
7 Execution timed out 8077 ms 84048 KB Time limit exceeded
8 Runtime error 66 ms 131072 KB Execution killed with signal 9
9 Runtime error 76 ms 131072 KB Execution killed with signal 9
10 Runtime error 74 ms 131072 KB Execution killed with signal 9
11 Runtime error 105 ms 131072 KB Execution killed with signal 9
12 Runtime error 81 ms 131072 KB Execution killed with signal 9
13 Runtime error 82 ms 131072 KB Execution killed with signal 9
14 Runtime error 82 ms 131072 KB Execution killed with signal 9
15 Runtime error 85 ms 131072 KB Execution killed with signal 9
16 Runtime error 82 ms 131072 KB Execution killed with signal 9
17 Runtime error 85 ms 131072 KB Execution killed with signal 9