oj.uz

Submission #763768

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

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

const int BIG = 300;
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 0 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 7 ms 336 KB Output is correct
6 Correct 14 ms 544 KB Output is correct
7 Correct 26 ms 560 KB Output is correct
8 Correct 28 ms 704 KB Output is correct
9 Correct 36 ms 1352 KB Output is correct
10 Correct 83 ms 1724 KB Output is correct
11 Correct 125 ms 2268 KB Output is correct
12 Correct 126 ms 3112 KB Output is correct
13 Correct 135 ms 3392 KB Output is correct
14 Correct 276 ms 3828 KB Output is correct
15 Correct 286 ms 7552 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8036 ms 42280 KB Time limit exceeded
2 Correct 7429 ms 33488 KB Output is correct
3 Correct 7199 ms 35788 KB Output is correct
4 Correct 280 ms 5084 KB Output is correct
5 Correct 313 ms 7732 KB Output is correct
6 Execution timed out 8021 ms 53152 KB Time limit exceeded
7 Execution timed out 8047 ms 54224 KB Time limit exceeded
8 Execution timed out 8028 ms 110892 KB Time limit exceeded
9 Execution timed out 8007 ms 94740 KB Time limit exceeded
10 Runtime error 95 ms 131072 KB Execution killed with signal 9
11 Runtime error 100 ms 131072 KB Execution killed with signal 9
12 Correct 3865 ms 32240 KB Output is correct
13 Correct 4503 ms 35192 KB Output is correct
14 Execution timed out 8007 ms 75360 KB Time limit exceeded
15 Correct 5780 ms 46352 KB Output is correct
16 Correct 6103 ms 55200 KB Output is correct
17 Execution timed out 8026 ms 84236 KB Time limit exceeded