oj.uz

답안 #763775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763775 2023-06-22T20:45:43 Z izanbf Regions (IOI09_regions) C++14
100 / 100
 4473 ms 57968 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, 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 = vvi(bigs, vi(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 208 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 13 ms 616 KB Output is correct
7 Correct 29 ms 556 KB Output is correct
8 Correct 33 ms 692 KB Output is correct
9 Correct 37 ms 1332 KB Output is correct
10 Correct 76 ms 1652 KB Output is correct
11 Correct 100 ms 2384 KB Output is correct
12 Correct 130 ms 3016 KB Output is correct
13 Correct 187 ms 3320 KB Output is correct
14 Correct 235 ms 3956 KB Output is correct
15 Correct 307 ms 7336 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1006 ms 11904 KB Output is correct
2 Correct 1332 ms 12516 KB Output is correct
3 Correct 1828 ms 18364 KB Output is correct
4 Correct 281 ms 5228 KB Output is correct
5 Correct 283 ms 7752 KB Output is correct
6 Correct 475 ms 7976 KB Output is correct
7 Correct 497 ms 9224 KB Output is correct
8 Correct 1206 ms 18632 KB Output is correct
9 Correct 2346 ms 25132 KB Output is correct
10 Correct 3990 ms 34120 KB Output is correct
11 Correct 4473 ms 33292 KB Output is correct
12 Correct 1427 ms 24100 KB Output is correct
13 Correct 2001 ms 27216 KB Output is correct
14 Correct 2410 ms 41404 KB Output is correct
15 Correct 3245 ms 37296 KB Output is correct
16 Correct 2763 ms 46468 KB Output is correct
17 Correct 2569 ms 57968 KB Output is correct