oj.uz

Submission #230697

# Submission time Handle Problem Language Result Execution time Memory
230697 2020-05-11T07:55:03 Z WLZ Capital City (JOI20_capital_city) C++14
100 / 100
 1419 ms 51992 KB 
#include "bits/stdc++.h"
using namespace std;

const int INF = 0x3f3f3f3f;

int k, ans = INF;
vector< vector<int> > g, towns;
vector<int> c, sz, par, cur;
vector<bool> used;

void dfs(int u, int p, vector<int> &out) {
    sz[u] = 1; par[u] = p;
    out.push_back(u);
    for (auto& v : g[u]) {
        if (v != p && !used[v]) {
            dfs(v, u, out);
            sz[u] += sz[v];
        }
    }
}

int find_centroid(int u, int p, int n) {
    for (auto& v : g[u]) {
        if (v != p && sz[v] > n / 2 && !used[v]) {
            return find_centroid(v, u, n);
        }
    }
    return u;
}

void solve(int u) {
    vector<int> junk;
    dfs(u, -1, junk);
    int centroid = find_centroid(u, -1, sz[u]);
    dfs(centroid, -1, cur);
    map<int, int> cnt;
    for (auto& x : cur) {
        cnt[c[x]]++;
    }
    set<int> st;
    if (cnt[c[centroid]] == (int) towns[c[centroid]].size()) {
        bool pos = true;
        queue<int> q;
        for (auto& x : towns[c[centroid]]) {
            q.push(x);
        }
        st.insert(c[centroid]);
        while (!q.empty()) {
            int x = q.front(); q.pop();
            if (x != centroid && !st.count(c[par[x]])) {
                if (cnt[c[par[x]]] != (int) towns[c[par[x]]].size()) {
                    pos = false;
                    break;
                }
                for (auto& y : towns[c[par[x]]]) {
                    q.push(y);
                }
                st.insert(c[par[x]]);
            }
        }
        if (pos) {
            ans = min(ans, (int) st.size());
        }
    }
    used[centroid] = true;
    cur.clear();
    for (auto& v : g[centroid]) {
        if (!used[v]) {
            solve(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n >> k;
    g.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    c.resize(n + 1);
    towns.resize(k + 1);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        towns[c[i]].push_back(i);
    }
    par.resize(n + 1);
    sz.resize(n + 1);
    used.assign(n + 1, false);
    solve(1);
    cout << ans - 1 << '\n';
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 8 ms 640 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 9 ms 768 KB Output is correct
16 Correct 9 ms 768 KB Output is correct
17 Correct 7 ms 640 KB Output is correct
18 Correct 7 ms 640 KB Output is correct
19 Correct 7 ms 640 KB Output is correct
20 Correct 7 ms 640 KB Output is correct
21 Correct 7 ms 640 KB Output is correct
22 Correct 9 ms 896 KB Output is correct
23 Correct 9 ms 768 KB Output is correct
24 Correct 9 ms 768 KB Output is correct
25 Correct 9 ms 768 KB Output is correct
26 Correct 9 ms 896 KB Output is correct
27 Correct 9 ms 768 KB Output is correct
28 Correct 9 ms 640 KB Output is correct
29 Correct 9 ms 768 KB Output is correct
30 Correct 9 ms 768 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1419 ms 51588 KB Output is correct
2 Correct 706 ms 51992 KB Output is correct
3 Correct 1368 ms 51184 KB Output is correct
4 Correct 708 ms 51880 KB Output is correct
5 Correct 1313 ms 48336 KB Output is correct
6 Correct 699 ms 51792 KB Output is correct
7 Correct 1281 ms 48184 KB Output is correct
8 Correct 643 ms 50360 KB Output is correct
9 Correct 1105 ms 39280 KB Output is correct
10 Correct 1160 ms 37376 KB Output is correct
11 Correct 1129 ms 39700 KB Output is correct
12 Correct 1125 ms 41744 KB Output is correct
13 Correct 1114 ms 37228 KB Output is correct
14 Correct 1156 ms 42108 KB Output is correct
15 Correct 1184 ms 41756 KB Output is correct
16 Correct 1112 ms 37732 KB Output is correct
17 Correct 1110 ms 38484 KB Output is correct
18 Correct 1113 ms 38324 KB Output is correct
19 Correct 1160 ms 40880 KB Output is correct
20 Correct 1110 ms 42744 KB Output is correct
21 Correct 5 ms 384 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 8 ms 640 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 9 ms 768 KB Output is correct
16 Correct 9 ms 768 KB Output is correct
17 Correct 7 ms 640 KB Output is correct
18 Correct 7 ms 640 KB Output is correct
19 Correct 7 ms 640 KB Output is correct
20 Correct 7 ms 640 KB Output is correct
21 Correct 7 ms 640 KB Output is correct
22 Correct 9 ms 896 KB Output is correct
23 Correct 9 ms 768 KB Output is correct
24 Correct 9 ms 768 KB Output is correct
25 Correct 9 ms 768 KB Output is correct
26 Correct 9 ms 896 KB Output is correct
27 Correct 9 ms 768 KB Output is correct
28 Correct 9 ms 640 KB Output is correct
29 Correct 9 ms 768 KB Output is correct
30 Correct 9 ms 768 KB Output is correct
31 Correct 1419 ms 51588 KB Output is correct
32 Correct 706 ms 51992 KB Output is correct
33 Correct 1368 ms 51184 KB Output is correct
34 Correct 708 ms 51880 KB Output is correct
35 Correct 1313 ms 48336 KB Output is correct
36 Correct 699 ms 51792 KB Output is correct
37 Correct 1281 ms 48184 KB Output is correct
38 Correct 643 ms 50360 KB Output is correct
39 Correct 1105 ms 39280 KB Output is correct
40 Correct 1160 ms 37376 KB Output is correct
41 Correct 1129 ms 39700 KB Output is correct
42 Correct 1125 ms 41744 KB Output is correct
43 Correct 1114 ms 37228 KB Output is correct
44 Correct 1156 ms 42108 KB Output is correct
45 Correct 1184 ms 41756 KB Output is correct
46 Correct 1112 ms 37732 KB Output is correct
47 Correct 1110 ms 38484 KB Output is correct
48 Correct 1113 ms 38324 KB Output is correct
49 Correct 1160 ms 40880 KB Output is correct
50 Correct 1110 ms 42744 KB Output is correct
51 Correct 5 ms 384 KB Output is correct
52 Correct 844 ms 25300 KB Output is correct
53 Correct 898 ms 25712 KB Output is correct
54 Correct 909 ms 25400 KB Output is correct
55 Correct 920 ms 25584 KB Output is correct
56 Correct 925 ms 25836 KB Output is correct
57 Correct 918 ms 26108 KB Output is correct
58 Correct 1099 ms 35748 KB Output is correct
59 Correct 973 ms 34684 KB Output is correct
60 Correct 1172 ms 37536 KB Output is correct
61 Correct 1293 ms 38012 KB Output is correct
62 Correct 713 ms 51904 KB Output is correct
63 Correct 683 ms 51928 KB Output is correct
64 Correct 653 ms 50700 KB Output is correct
65 Correct 697 ms 51688 KB Output is correct
66 Correct 491 ms 34620 KB Output is correct
67 Correct 455 ms 34256 KB Output is correct
68 Correct 469 ms 34488 KB Output is correct
69 Correct 514 ms 35256 KB Output is correct
70 Correct 482 ms 35268 KB Output is correct
71 Correct 509 ms 34468 KB Output is correct
72 Correct 542 ms 35260 KB Output is correct
73 Correct 467 ms 33752 KB Output is correct
74 Correct 516 ms 35344 KB Output is correct
75 Correct 498 ms 35528 KB Output is correct
76 Correct 1381 ms 41964 KB Output is correct
77 Correct 1328 ms 41056 KB Output is correct
78 Correct 1173 ms 38288 KB Output is correct
79 Correct 1120 ms 36648 KB Output is correct
80 Correct 1057 ms 42284 KB Output is correct
81 Correct 1164 ms 39552 KB Output is correct
82 Correct 1098 ms 39732 KB Output is correct
83 Correct 1083 ms 36868 KB Output is correct
84 Correct 1173 ms 41644 KB Output is correct
85 Correct 1104 ms 40644 KB Output is correct
86 Correct 1073 ms 36544 KB Output is correct
87 Correct 1090 ms 38364 KB Output is correct
88 Correct 974 ms 37996 KB Output is correct
89 Correct 933 ms 34788 KB Output is correct
90 Correct 939 ms 34744 KB Output is correct
91 Correct 935 ms 36464 KB Output is correct
92 Correct 999 ms 35544 KB Output is correct
93 Correct 975 ms 35284 KB Output is correct
94 Correct 982 ms 34712 KB Output is correct
95 Correct 973 ms 35992 KB Output is correct
96 Correct 1002 ms 34984 KB Output is correct
97 Correct 1010 ms 36588 KB Output is correct