oj.uz

답안 #763769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763769 2023-06-22T20:38:00 Z izanbf Regions (IOI09_regions) C++14
80 / 100
 8000 ms 83784 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int BIG = 600;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 4 ms 352 KB Output is correct
5 Correct 9 ms 404 KB Output is correct
6 Correct 18 ms 520 KB Output is correct
7 Correct 20 ms 596 KB Output is correct
8 Correct 26 ms 624 KB Output is correct
9 Correct 47 ms 1308 KB Output is correct
10 Correct 56 ms 1704 KB Output is correct
11 Correct 104 ms 2192 KB Output is correct
12 Correct 151 ms 3136 KB Output is correct
13 Correct 193 ms 3328 KB Output is correct
14 Correct 295 ms 3852 KB Output is correct
15 Correct 230 ms 7388 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5238 ms 23316 KB Output is correct
2 Execution timed out 8048 ms 29404 KB Time limit exceeded
3 Execution timed out 8007 ms 34352 KB Time limit exceeded
4 Correct 239 ms 5116 KB Output is correct
5 Correct 219 ms 7800 KB Output is correct
6 Correct 461 ms 7976 KB Output is correct
7 Correct 618 ms 9212 KB Output is correct
8 Correct 1204 ms 18688 KB Output is correct
9 Correct 2720 ms 25192 KB Output is correct
10 Correct 3973 ms 34064 KB Output is correct
11 Correct 4969 ms 33376 KB Output is correct
12 Correct 3863 ms 32240 KB Output is correct
13 Correct 4998 ms 35344 KB Output is correct
14 Execution timed out 8042 ms 64364 KB Time limit exceeded
15 Correct 6320 ms 46348 KB Output is correct
16 Correct 5437 ms 55276 KB Output is correct
17 Execution timed out 8090 ms 83784 KB Time limit exceeded