oj.uz

Submission #559475

# Submission time Handle Problem Language Result Execution time Memory
559475 2022-05-10T01:40:49 Z dooompy Capital City (JOI20_capital_city) C++17
100 / 100
 1159 ms 49252 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

vector<int> adj[200005];
int city[200005];
vector<int> col[200005];
bool centroid[200005];
int sz[200005], par[200005];
vector<int> curcol[200005];
int ans; int n; int timer;
int seen[200005];

void dfs(int node, int p = -1) {

    sz[node] = 1;
    curcol[city[node]].push_back(node);

    for (auto nxt : adj[node]) {
        if (nxt == p || centroid[nxt]) continue;
        dfs(nxt, node);
        sz[node] += sz[nxt];
        par[nxt] = node;
    }
}

int find_centroid(int node, int p, int n) {

    for (auto nxt : adj[node]) {
        if (nxt == p || centroid[nxt]) continue;
        if (sz[nxt] * 2 >= n) return find_centroid(nxt, node, n);
    }

    return node;
}

void clear(int node, int p = -1) {
    curcol[city[node]].clear();

    for (auto nxt : adj[node]) {
        if (nxt == p || centroid[nxt]) continue;
        clear(nxt, node);
    }
}

void solve(int node) {
    dfs(node);

    int cent = find_centroid(node, -1, sz[node]);

    clear(node);

    dfs(cent);

    queue<int> q;
    q.push(city[cent]);

    int ct = 0;
    timer++;

    seen[city[cent]] = timer;

    while (!q.empty()) {
        ct++;
        auto cur = q.front(); q.pop();
        if (curcol[cur].size() != col[cur].size()) {
            ct = n; break;
        }

        for (auto nd : curcol[cur]) {
            if (nd == cent) continue;

            int p = city[par[nd]];
            if (seen[p] == timer) continue;
            seen[p] = timer;
            q.push(p);
        }
    }

    ans = min(ans, ct - 1);

    clear(cent);
    centroid[cent] = true;

    for (auto nxt : adj[cent]) {
        if (!centroid[nxt]) solve(nxt);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int k; cin >> n >> k; ans = n;

    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        cin >> city[i];
        col[city[i]].push_back(i);
    }

    solve(1);

    cout << ans << "\n";
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14332 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14372 KB Output is correct
6 Correct 10 ms 14428 KB Output is correct
7 Correct 9 ms 14432 KB Output is correct
8 Correct 10 ms 14496 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14332 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14372 KB Output is correct
6 Correct 10 ms 14428 KB Output is correct
7 Correct 9 ms 14432 KB Output is correct
8 Correct 10 ms 14496 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 9 ms 14568 KB Output is correct
12 Correct 10 ms 14568 KB Output is correct
13 Correct 10 ms 14548 KB Output is correct
14 Correct 10 ms 14548 KB Output is correct
15 Correct 10 ms 14548 KB Output is correct
16 Correct 10 ms 14548 KB Output is correct
17 Correct 10 ms 14548 KB Output is correct
18 Correct 10 ms 14568 KB Output is correct
19 Correct 10 ms 14628 KB Output is correct
20 Correct 10 ms 14544 KB Output is correct
21 Correct 11 ms 14656 KB Output is correct
22 Correct 11 ms 14724 KB Output is correct
23 Correct 10 ms 14676 KB Output is correct
24 Correct 9 ms 14572 KB Output is correct
25 Correct 10 ms 14688 KB Output is correct
26 Correct 11 ms 14636 KB Output is correct
27 Correct 10 ms 14692 KB Output is correct
28 Correct 11 ms 14696 KB Output is correct
29 Correct 10 ms 14548 KB Output is correct
30 Correct 10 ms 14612 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1159 ms 48692 KB Output is correct
2 Correct 295 ms 49192 KB Output is correct
3 Correct 1112 ms 48484 KB Output is correct
4 Correct 321 ms 49100 KB Output is correct
5 Correct 957 ms 45184 KB Output is correct
6 Correct 320 ms 49052 KB Output is correct
7 Correct 1040 ms 45384 KB Output is correct
8 Correct 309 ms 48200 KB Output is correct
9 Correct 1052 ms 42624 KB Output is correct
10 Correct 1032 ms 40140 KB Output is correct
11 Correct 1064 ms 43164 KB Output is correct
12 Correct 1082 ms 45832 KB Output is correct
13 Correct 1059 ms 39804 KB Output is correct
14 Correct 1099 ms 46072 KB Output is correct
15 Correct 1068 ms 45752 KB Output is correct
16 Correct 1062 ms 40772 KB Output is correct
17 Correct 1062 ms 41328 KB Output is correct
18 Correct 1080 ms 41660 KB Output is correct
19 Correct 1100 ms 44716 KB Output is correct
20 Correct 1012 ms 46984 KB Output is correct
21 Correct 8 ms 14420 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14332 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14372 KB Output is correct
6 Correct 10 ms 14428 KB Output is correct
7 Correct 9 ms 14432 KB Output is correct
8 Correct 10 ms 14496 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 9 ms 14568 KB Output is correct
12 Correct 10 ms 14568 KB Output is correct
13 Correct 10 ms 14548 KB Output is correct
14 Correct 10 ms 14548 KB Output is correct
15 Correct 10 ms 14548 KB Output is correct
16 Correct 10 ms 14548 KB Output is correct
17 Correct 10 ms 14548 KB Output is correct
18 Correct 10 ms 14568 KB Output is correct
19 Correct 10 ms 14628 KB Output is correct
20 Correct 10 ms 14544 KB Output is correct
21 Correct 11 ms 14656 KB Output is correct
22 Correct 11 ms 14724 KB Output is correct
23 Correct 10 ms 14676 KB Output is correct
24 Correct 9 ms 14572 KB Output is correct
25 Correct 10 ms 14688 KB Output is correct
26 Correct 11 ms 14636 KB Output is correct
27 Correct 10 ms 14692 KB Output is correct
28 Correct 11 ms 14696 KB Output is correct
29 Correct 10 ms 14548 KB Output is correct
30 Correct 10 ms 14612 KB Output is correct
31 Correct 1159 ms 48692 KB Output is correct
32 Correct 295 ms 49192 KB Output is correct
33 Correct 1112 ms 48484 KB Output is correct
34 Correct 321 ms 49100 KB Output is correct
35 Correct 957 ms 45184 KB Output is correct
36 Correct 320 ms 49052 KB Output is correct
37 Correct 1040 ms 45384 KB Output is correct
38 Correct 309 ms 48200 KB Output is correct
39 Correct 1052 ms 42624 KB Output is correct
40 Correct 1032 ms 40140 KB Output is correct
41 Correct 1064 ms 43164 KB Output is correct
42 Correct 1082 ms 45832 KB Output is correct
43 Correct 1059 ms 39804 KB Output is correct
44 Correct 1099 ms 46072 KB Output is correct
45 Correct 1068 ms 45752 KB Output is correct
46 Correct 1062 ms 40772 KB Output is correct
47 Correct 1062 ms 41328 KB Output is correct
48 Correct 1080 ms 41660 KB Output is correct
49 Correct 1100 ms 44716 KB Output is correct
50 Correct 1012 ms 46984 KB Output is correct
51 Correct 8 ms 14420 KB Output is correct
52 Correct 737 ms 30044 KB Output is correct
53 Correct 796 ms 30036 KB Output is correct
54 Correct 729 ms 30016 KB Output is correct
55 Correct 785 ms 30156 KB Output is correct
56 Correct 755 ms 30076 KB Output is correct
57 Correct 757 ms 30088 KB Output is correct
58 Correct 745 ms 34800 KB Output is correct
59 Correct 773 ms 35144 KB Output is correct
60 Correct 1026 ms 34924 KB Output is correct
61 Correct 988 ms 34492 KB Output is correct
62 Correct 302 ms 49252 KB Output is correct
63 Correct 314 ms 49148 KB Output is correct
64 Correct 300 ms 48588 KB Output is correct
65 Correct 316 ms 49052 KB Output is correct
66 Correct 467 ms 39380 KB Output is correct
67 Correct 537 ms 39272 KB Output is correct
68 Correct 463 ms 39280 KB Output is correct
69 Correct 551 ms 39284 KB Output is correct
70 Correct 513 ms 39168 KB Output is correct
71 Correct 533 ms 39196 KB Output is correct
72 Correct 472 ms 39172 KB Output is correct
73 Correct 503 ms 38380 KB Output is correct
74 Correct 496 ms 39336 KB Output is correct
75 Correct 521 ms 39244 KB Output is correct
76 Correct 857 ms 39216 KB Output is correct
77 Correct 850 ms 37452 KB Output is correct
78 Correct 1074 ms 41360 KB Output is correct
79 Correct 1076 ms 39184 KB Output is correct
80 Correct 1069 ms 46412 KB Output is correct
81 Correct 1031 ms 42772 KB Output is correct
82 Correct 996 ms 42996 KB Output is correct
83 Correct 972 ms 39588 KB Output is correct
84 Correct 1107 ms 45620 KB Output is correct
85 Correct 1020 ms 44032 KB Output is correct
86 Correct 1016 ms 39164 KB Output is correct
87 Correct 1004 ms 41008 KB Output is correct
88 Correct 931 ms 42088 KB Output is correct
89 Correct 930 ms 38064 KB Output is correct
90 Correct 861 ms 37912 KB Output is correct
91 Correct 936 ms 40304 KB Output is correct
92 Correct 978 ms 39132 KB Output is correct
93 Correct 948 ms 38664 KB Output is correct
94 Correct 937 ms 38092 KB Output is correct
95 Correct 969 ms 39448 KB Output is correct
96 Correct 989 ms 38208 KB Output is correct
97 Correct 995 ms 40308 KB Output is correct