oj.uz

Submission #898487

# Submission time Handle Problem Language Result Execution time Memory
898487 2024-01-04T18:18:30 Z box Capital City (JOI20_capital_city) C++17
100 / 100
 762 ms 149900 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define bug(x) cerr << "L" << __LINE__ << " | " << #x << " = " << x << endl;
#else
#define bug(x)
#define cerr if (0) cerr
#endif

#define ar array
#define sz(v) int(std::size(v))
#define all(v) std::begin(v), std::end(v)
using i64 = long long;
using vi = vector<int>;
using pi = pair<int, int>;

const int MAXN = 2e5;

int N, K, C[MAXN];
vi adj[MAXN], who[MAXN];
int num;
int cnt[MAXN], child[MAXN], parent[MAXN], depth[MAXN], root[MAXN];

const int MAXS = MAXN * 3;

vi g[MAXS], rg[MAXS], order;
int id[MAXS], colors[MAXN];

void dfs_ord(int i) {
    id[i] = 0;
    for (int j : g[i]) if (id[j] == -1) dfs_ord(j);
    order.push_back(i);
}

void dfs_id(int i, int c) {
    id[i] = c;
    for (int j : rg[i]) if (id[j] == -1) dfs_id(j, c);
}

void make_edge(int i, int j) {
    g[i].push_back(j);
    rg[j].push_back(i);
}

struct segt {
    int l, r;
    segt *lc = NULL, *rc = NULL;
    int id;
    segt(int l, int r) : l(l), r(r) {
        id = num++;
        if (l < r) {
            int m = (l + r) / 2;
            lc = new segt(l, m);
            rc = new segt(m + 1, r);
            make_edge(lc->id, id);
            make_edge(rc->id, id);
        }
    }
    void qry(int ql, int qr, vi& v) {
        if (ql <= l && qr >= r) v.push_back(id);
        else {
            if (ql <= lc->r) lc->qry(ql, qr, v);
            if (qr >= rc->l) rc->qry(ql, qr, v);
        }
    }
} *ids[MAXN];

vi qry(int i, int l, int r) {
    vi v;
    ids[i]->qry(l, r, v);
    return v;
}

int dfs_sz(int i) {
    int s = 1, x = 0;
    child[i] = -1;
    for (int j : adj[i]) if (parent[i] != j) {
        parent[j] = i;
        depth[j] = depth[i] + 1;
        int y = dfs_sz(j);
        if (y > x) x = y, child[i] = j;
        s += y;
    }
    return s;
}

void dfs_hvy(int r, int i) {
    cnt[root[i] = r]++;
    if (~child[i]) dfs_hvy(r, child[i]);
    for (int j : adj[i]) if (parent[i] != j && child[i] != j) dfs_hvy(j, j);
}

int lca(int i, int j) {
    while (root[i] != root[j]) {
        if (depth[root[i]] < depth[root[j]]) swap(i, j);
        i = parent[root[i]];
    }
    return depth[i] < depth[j] ? i : j;
}

void make_path(int p, int i, vi& v) {
    while (root[i] != root[p]) {
        int r = root[i];
        ids[r]->qry(0, depth[i] - depth[r], v);
        i = parent[r];
    }
    int r = root[i];
    ids[r]->qry(depth[p] - depth[r], depth[i] - depth[r], v);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    for (int h = 0; h < N - 1; h++) {
        int i, j; cin >> i >> j, i--, j--;
        adj[i].push_back(j), adj[j].push_back(i);
    }
    for (int i = 0; i < N; i++) {
        cin >> C[i], C[i]--;
        who[C[i]].push_back(i);
    }
    num = K;
    parent[0] = -1;
    dfs_sz(0);
    dfs_hvy(0, 0);
    for (int i = 0; i < N; i++) if (root[i] == i) ids[i] = new segt(0, cnt[i] - 1);
    assert(num <= MAXS);
    for (int i = 0; i < N; i++) {
        int r = root[i];
        for (int v : qry(r, depth[i] - depth[r], depth[i] - depth[r]))
            make_edge(C[i], v);
    }
    for (int c = 0; c < K; c++) {
        int top = who[c].at(0);
        for (int i : who[c]) top = lca(top, i);
        vi v;
        for (int i : who[c]) make_path(top, i, v);
        for (int u : v) make_edge(u, c);
    }
    fill(id, id + num, -1);
    for (int i = 0; i < num; i++) if (id[i] == -1) dfs_ord(i);
    reverse(all(order));
    fill(id, id + num, -1);
    int c = 0;
    for (int i : order) if (id[i] == -1) dfs_id(i, c++);
    for (int c = 0; c < K; c++) colors[id[c]]++;
    for (int i = 0; i < num; i++) for (int j : g[i]) if (id[i] != id[j]) colors[id[j]] = INT_MAX;
    int ans = INT_MAX;
    for (int c = 0; c < K; c++) ans = min(ans, colors[id[c]] - 1);
    cout << ans << '\n';

}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 46428 KB Output is correct
2 Correct 10 ms 46396 KB Output is correct
3 Correct 9 ms 46428 KB Output is correct
4 Correct 10 ms 46428 KB Output is correct
5 Correct 10 ms 46424 KB Output is correct
6 Correct 9 ms 46428 KB Output is correct
7 Correct 9 ms 46476 KB Output is correct
8 Correct 9 ms 46428 KB Output is correct
9 Correct 9 ms 46428 KB Output is correct
10 Correct 10 ms 46428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 46428 KB Output is correct
2 Correct 10 ms 46396 KB Output is correct
3 Correct 9 ms 46428 KB Output is correct
4 Correct 10 ms 46428 KB Output is correct
5 Correct 10 ms 46424 KB Output is correct
6 Correct 9 ms 46428 KB Output is correct
7 Correct 9 ms 46476 KB Output is correct
8 Correct 9 ms 46428 KB Output is correct
9 Correct 9 ms 46428 KB Output is correct
10 Correct 10 ms 46428 KB Output is correct
11 Correct 11 ms 46940 KB Output is correct
12 Correct 12 ms 47088 KB Output is correct
13 Correct 12 ms 46936 KB Output is correct
14 Correct 13 ms 46864 KB Output is correct
15 Correct 13 ms 46940 KB Output is correct
16 Correct 12 ms 47096 KB Output is correct
17 Correct 13 ms 46940 KB Output is correct
18 Correct 12 ms 47196 KB Output is correct
19 Correct 12 ms 46936 KB Output is correct
20 Correct 11 ms 47196 KB Output is correct
21 Correct 11 ms 47196 KB Output is correct
22 Correct 12 ms 47196 KB Output is correct
23 Correct 13 ms 47196 KB Output is correct
24 Correct 12 ms 46940 KB Output is correct
25 Correct 12 ms 47244 KB Output is correct
26 Correct 12 ms 47196 KB Output is correct
27 Correct 12 ms 47196 KB Output is correct
28 Correct 13 ms 47188 KB Output is correct
29 Correct 12 ms 47192 KB Output is correct
30 Correct 12 ms 47196 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 139984 KB Output is correct
2 Correct 339 ms 140384 KB Output is correct
3 Correct 738 ms 140076 KB Output is correct
4 Correct 344 ms 140216 KB Output is correct
5 Correct 710 ms 138360 KB Output is correct
6 Correct 345 ms 144048 KB Output is correct
7 Correct 678 ms 142004 KB Output is correct
8 Correct 326 ms 141600 KB Output is correct
9 Correct 591 ms 132352 KB Output is correct
10 Correct 579 ms 129160 KB Output is correct
11 Correct 571 ms 133204 KB Output is correct
12 Correct 589 ms 134968 KB Output is correct
13 Correct 579 ms 127524 KB Output is correct
14 Correct 577 ms 135480 KB Output is correct
15 Correct 594 ms 134416 KB Output is correct
16 Correct 579 ms 131476 KB Output is correct
17 Correct 600 ms 131400 KB Output is correct
18 Correct 571 ms 131480 KB Output is correct
19 Correct 591 ms 133520 KB Output is correct
20 Correct 566 ms 135224 KB Output is correct
21 Correct 9 ms 46424 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 46428 KB Output is correct
2 Correct 10 ms 46396 KB Output is correct
3 Correct 9 ms 46428 KB Output is correct
4 Correct 10 ms 46428 KB Output is correct
5 Correct 10 ms 46424 KB Output is correct
6 Correct 9 ms 46428 KB Output is correct
7 Correct 9 ms 46476 KB Output is correct
8 Correct 9 ms 46428 KB Output is correct
9 Correct 9 ms 46428 KB Output is correct
10 Correct 10 ms 46428 KB Output is correct
11 Correct 11 ms 46940 KB Output is correct
12 Correct 12 ms 47088 KB Output is correct
13 Correct 12 ms 46936 KB Output is correct
14 Correct 13 ms 46864 KB Output is correct
15 Correct 13 ms 46940 KB Output is correct
16 Correct 12 ms 47096 KB Output is correct
17 Correct 13 ms 46940 KB Output is correct
18 Correct 12 ms 47196 KB Output is correct
19 Correct 12 ms 46936 KB Output is correct
20 Correct 11 ms 47196 KB Output is correct
21 Correct 11 ms 47196 KB Output is correct
22 Correct 12 ms 47196 KB Output is correct
23 Correct 13 ms 47196 KB Output is correct
24 Correct 12 ms 46940 KB Output is correct
25 Correct 12 ms 47244 KB Output is correct
26 Correct 12 ms 47196 KB Output is correct
27 Correct 12 ms 47196 KB Output is correct
28 Correct 13 ms 47188 KB Output is correct
29 Correct 12 ms 47192 KB Output is correct
30 Correct 12 ms 47196 KB Output is correct
31 Correct 762 ms 139984 KB Output is correct
32 Correct 339 ms 140384 KB Output is correct
33 Correct 738 ms 140076 KB Output is correct
34 Correct 344 ms 140216 KB Output is correct
35 Correct 710 ms 138360 KB Output is correct
36 Correct 345 ms 144048 KB Output is correct
37 Correct 678 ms 142004 KB Output is correct
38 Correct 326 ms 141600 KB Output is correct
39 Correct 591 ms 132352 KB Output is correct
40 Correct 579 ms 129160 KB Output is correct
41 Correct 571 ms 133204 KB Output is correct
42 Correct 589 ms 134968 KB Output is correct
43 Correct 579 ms 127524 KB Output is correct
44 Correct 577 ms 135480 KB Output is correct
45 Correct 594 ms 134416 KB Output is correct
46 Correct 579 ms 131476 KB Output is correct
47 Correct 600 ms 131400 KB Output is correct
48 Correct 571 ms 131480 KB Output is correct
49 Correct 591 ms 133520 KB Output is correct
50 Correct 566 ms 135224 KB Output is correct
51 Correct 9 ms 46424 KB Output is correct
52 Correct 471 ms 109796 KB Output is correct
53 Correct 503 ms 110524 KB Output is correct
54 Correct 483 ms 110340 KB Output is correct
55 Correct 484 ms 110200 KB Output is correct
56 Correct 461 ms 109780 KB Output is correct
57 Correct 480 ms 110736 KB Output is correct
58 Correct 542 ms 112224 KB Output is correct
59 Correct 507 ms 111812 KB Output is correct
60 Correct 567 ms 115092 KB Output is correct
61 Correct 594 ms 116972 KB Output is correct
62 Correct 348 ms 143892 KB Output is correct
63 Correct 342 ms 143912 KB Output is correct
64 Correct 331 ms 144660 KB Output is correct
65 Correct 339 ms 143988 KB Output is correct
66 Correct 424 ms 149900 KB Output is correct
67 Correct 390 ms 120332 KB Output is correct
68 Correct 416 ms 145220 KB Output is correct
69 Correct 433 ms 143408 KB Output is correct
70 Correct 425 ms 141364 KB Output is correct
71 Correct 424 ms 145228 KB Output is correct
72 Correct 426 ms 146476 KB Output is correct
73 Correct 419 ms 121192 KB Output is correct
74 Correct 429 ms 140608 KB Output is correct
75 Correct 448 ms 147656 KB Output is correct
76 Correct 448 ms 107376 KB Output is correct
77 Correct 434 ms 105676 KB Output is correct
78 Correct 591 ms 129284 KB Output is correct
79 Correct 571 ms 127236 KB Output is correct
80 Correct 576 ms 135220 KB Output is correct
81 Correct 589 ms 131816 KB Output is correct
82 Correct 578 ms 132012 KB Output is correct
83 Correct 556 ms 126676 KB Output is correct
84 Correct 617 ms 132356 KB Output is correct
85 Correct 583 ms 133632 KB Output is correct
86 Correct 586 ms 130244 KB Output is correct
87 Correct 584 ms 131084 KB Output is correct
88 Correct 546 ms 127396 KB Output is correct
89 Correct 544 ms 124040 KB Output is correct
90 Correct 524 ms 122108 KB Output is correct
91 Correct 538 ms 124060 KB Output is correct
92 Correct 554 ms 125704 KB Output is correct
93 Correct 568 ms 124616 KB Output is correct
94 Correct 545 ms 122988 KB Output is correct
95 Correct 529 ms 124724 KB Output is correct
96 Correct 537 ms 121500 KB Output is correct
97 Correct 550 ms 127712 KB Output is correct