oj.uz

Submission #778764

# Submission time Handle Problem Language Result Execution time Memory
778764 2023-07-10T16:20:16 Z raysh07 Capital City (JOI20_capital_city) C++17
100 / 100
 290 ms 65032 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 998244353;
 
struct DSU {
    vector<int> par, sz;
    DSU(int n): par(n) {
        iota(par.begin(), par.end(), 0);
        sz.assign(n, 1);
    }
 
    int find_set(int v) {
        return v == par[v] ? v : par[v] = find_set(par[v]);
    }
 
    bool union_sets(int a, int b) {
        if ((a = find_set(a)) == (b = find_set(b))) return false;
        if (sz[a] < sz[b]) swap(a, b);
        par[b] = a, sz[a] += sz[b], sz[b] = 0;
        return true;
    }
};
 
int n, k, col[N], my_out[N], tree_par[N], tree_st[N], tree_en[N], et[N];
vector<int> adj[N];
 
int tt = 0;
void dfs(int c, int p) {
    tree_par[c] = p;
    et[tree_st[c] = tt++] = c;
    for (int nxt : adj[c]) if (nxt != p) {
        dfs(nxt, c);
    }
    tree_en[c] = tt-1;
}
 
int par[N], min_st[N], max_st[N], cnt[N];
set<int> st[N];
multiset<int> ms[N];
 
void merge(int a, int b) {
    a = par[a], b = par[b];
    if (a == b) return;
    if (sz(st[a]) < sz(st[b])) swap(a, b);
 
    for (int x : st[b]) {
        ms[a].erase(x);
        st[a].insert(x);
        par[x] = a;
    }
    st[b].clear();
    cnt[a] += cnt[b];
 
    for (int x : ms[b]) {
        if (!st[a].count(x)) {
            ms[a].insert(x);
        }
    }
    ms[b].clear();
 
    min_st[a] = min(min_st[a], min_st[b]);
    max_st[a] = max(max_st[a], max_st[b]);
}
 
int get_out(int c) {
    c = par[c];
 
    int maybe = et[min_st[c]];
    int undo = -1;
    if (tree_par[maybe] != -1 && tree_en[maybe] >= max_st[c]) {
        undo = col[tree_par[maybe]];
        auto it = ms[c].find(undo);
        if (it != ms[c].end()) {
            ms[c].erase(it);
        } else {
            undo = -1;
        }
    }
 
    int ans = -1;
    if (sz(ms[c])) ans = *ms[c].begin();
 
    if (undo != -1) {
        ms[c].insert(undo);
    }
    return ans;
}
 
 
void solve() {
    cin >> n >> k;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b, --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }
    dfs(0, -1);
 
    for (int i = 0; i < n; i++) cin >> col[i], --col[i];
 
    for (int i = 0; i < k; i++) {
        par[i] = i;
        cnt[i] = 1;
        st[i].insert(i);
    }
 
    fill(min_st, min_st + n, MOD);
    fill(max_st, max_st + n, -1);
    for (int i = 0; i < n; i++) {
        min_st[col[i]] = min(min_st[col[i]], tree_st[i]);
        max_st[col[i]] = max(max_st[col[i]], tree_st[i]);
        if (tree_par[i] != -1 && col[tree_par[i]] != col[i]) {
            ms[col[i]].insert(col[tree_par[i]]);
        }
    }
 
    memset(my_out, -1, sizeof(my_out));
    DSU d(k);
    for (int root = 0; root < k; root++) {
        my_out[par[root]] = get_out(root);
        while (my_out[par[root]] != -1) {
            if (d.union_sets(root, my_out[par[root]])) {
                break;
            } else {
                vector<int> use{par[my_out[par[root]]]};
                while (use.back() != par[root]) {
                    use.push_back(par[my_out[use.back()]]);
                }
 
                use.pop_back();
                for (int x : use) {
                    merge(x, root);
                }
                my_out[par[root]] = get_out(root);
            }
        }
    }
 
    int best = MOD;
    for (int i = 0; i < k; i++) {
        int c = par[i];
        if (my_out[c] == -1) {
            best = min(best, cnt[c] - 1);
        }
    }
 
    cout << best << '\n';
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24544 KB Output is correct
2 Correct 13 ms 24596 KB Output is correct
3 Correct 13 ms 24612 KB Output is correct
4 Correct 12 ms 24532 KB Output is correct
5 Correct 13 ms 24532 KB Output is correct
6 Correct 13 ms 24624 KB Output is correct
7 Correct 12 ms 24532 KB Output is correct
8 Correct 13 ms 24628 KB Output is correct
9 Correct 13 ms 24532 KB Output is correct
10 Correct 14 ms 24564 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24544 KB Output is correct
2 Correct 13 ms 24596 KB Output is correct
3 Correct 13 ms 24612 KB Output is correct
4 Correct 12 ms 24532 KB Output is correct
5 Correct 13 ms 24532 KB Output is correct
6 Correct 13 ms 24624 KB Output is correct
7 Correct 12 ms 24532 KB Output is correct
8 Correct 13 ms 24628 KB Output is correct
9 Correct 13 ms 24532 KB Output is correct
10 Correct 14 ms 24564 KB Output is correct
11 Correct 14 ms 24788 KB Output is correct
12 Correct 14 ms 24788 KB Output is correct
13 Correct 15 ms 24836 KB Output is correct
14 Correct 14 ms 24788 KB Output is correct
15 Correct 14 ms 24852 KB Output is correct
16 Correct 14 ms 24860 KB Output is correct
17 Correct 13 ms 24856 KB Output is correct
18 Correct 14 ms 24788 KB Output is correct
19 Correct 13 ms 24860 KB Output is correct
20 Correct 14 ms 24788 KB Output is correct
21 Correct 14 ms 24856 KB Output is correct
22 Correct 13 ms 25016 KB Output is correct
23 Correct 14 ms 24860 KB Output is correct
24 Correct 13 ms 24840 KB Output is correct
25 Correct 14 ms 24916 KB Output is correct
26 Correct 15 ms 24968 KB Output is correct
27 Correct 14 ms 24916 KB Output is correct
28 Correct 15 ms 24856 KB Output is correct
29 Correct 13 ms 24916 KB Output is correct
30 Correct 14 ms 24860 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 64680 KB Output is correct
2 Correct 99 ms 65004 KB Output is correct
3 Correct 160 ms 64472 KB Output is correct
4 Correct 94 ms 65032 KB Output is correct
5 Correct 134 ms 61604 KB Output is correct
6 Correct 90 ms 64796 KB Output is correct
7 Correct 131 ms 60896 KB Output is correct
8 Correct 84 ms 62284 KB Output is correct
9 Correct 272 ms 59868 KB Output is correct
10 Correct 206 ms 58604 KB Output is correct
11 Correct 219 ms 60304 KB Output is correct
12 Correct 218 ms 61588 KB Output is correct
13 Correct 246 ms 57988 KB Output is correct
14 Correct 223 ms 61944 KB Output is correct
15 Correct 225 ms 61456 KB Output is correct
16 Correct 210 ms 58660 KB Output is correct
17 Correct 243 ms 58904 KB Output is correct
18 Correct 221 ms 59004 KB Output is correct
19 Correct 290 ms 60760 KB Output is correct
20 Correct 251 ms 62580 KB Output is correct
21 Correct 10 ms 24544 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24544 KB Output is correct
2 Correct 13 ms 24596 KB Output is correct
3 Correct 13 ms 24612 KB Output is correct
4 Correct 12 ms 24532 KB Output is correct
5 Correct 13 ms 24532 KB Output is correct
6 Correct 13 ms 24624 KB Output is correct
7 Correct 12 ms 24532 KB Output is correct
8 Correct 13 ms 24628 KB Output is correct
9 Correct 13 ms 24532 KB Output is correct
10 Correct 14 ms 24564 KB Output is correct
11 Correct 14 ms 24788 KB Output is correct
12 Correct 14 ms 24788 KB Output is correct
13 Correct 15 ms 24836 KB Output is correct
14 Correct 14 ms 24788 KB Output is correct
15 Correct 14 ms 24852 KB Output is correct
16 Correct 14 ms 24860 KB Output is correct
17 Correct 13 ms 24856 KB Output is correct
18 Correct 14 ms 24788 KB Output is correct
19 Correct 13 ms 24860 KB Output is correct
20 Correct 14 ms 24788 KB Output is correct
21 Correct 14 ms 24856 KB Output is correct
22 Correct 13 ms 25016 KB Output is correct
23 Correct 14 ms 24860 KB Output is correct
24 Correct 13 ms 24840 KB Output is correct
25 Correct 14 ms 24916 KB Output is correct
26 Correct 15 ms 24968 KB Output is correct
27 Correct 14 ms 24916 KB Output is correct
28 Correct 15 ms 24856 KB Output is correct
29 Correct 13 ms 24916 KB Output is correct
30 Correct 14 ms 24860 KB Output is correct
31 Correct 142 ms 64680 KB Output is correct
32 Correct 99 ms 65004 KB Output is correct
33 Correct 160 ms 64472 KB Output is correct
34 Correct 94 ms 65032 KB Output is correct
35 Correct 134 ms 61604 KB Output is correct
36 Correct 90 ms 64796 KB Output is correct
37 Correct 131 ms 60896 KB Output is correct
38 Correct 84 ms 62284 KB Output is correct
39 Correct 272 ms 59868 KB Output is correct
40 Correct 206 ms 58604 KB Output is correct
41 Correct 219 ms 60304 KB Output is correct
42 Correct 218 ms 61588 KB Output is correct
43 Correct 246 ms 57988 KB Output is correct
44 Correct 223 ms 61944 KB Output is correct
45 Correct 225 ms 61456 KB Output is correct
46 Correct 210 ms 58660 KB Output is correct
47 Correct 243 ms 58904 KB Output is correct
48 Correct 221 ms 59004 KB Output is correct
49 Correct 290 ms 60760 KB Output is correct
50 Correct 251 ms 62580 KB Output is correct
51 Correct 10 ms 24544 KB Output is correct
52 Correct 213 ms 50512 KB Output is correct
53 Correct 259 ms 50540 KB Output is correct
54 Correct 180 ms 50544 KB Output is correct
55 Correct 177 ms 50540 KB Output is correct
56 Correct 175 ms 50548 KB Output is correct
57 Correct 197 ms 50504 KB Output is correct
58 Correct 146 ms 55648 KB Output is correct
59 Correct 151 ms 55952 KB Output is correct
60 Correct 159 ms 56224 KB Output is correct
61 Correct 209 ms 55988 KB Output is correct
62 Correct 98 ms 64992 KB Output is correct
63 Correct 91 ms 65016 KB Output is correct
64 Correct 95 ms 62848 KB Output is correct
65 Correct 96 ms 64732 KB Output is correct
66 Correct 124 ms 52920 KB Output is correct
67 Correct 125 ms 52756 KB Output is correct
68 Correct 117 ms 52916 KB Output is correct
69 Correct 116 ms 52884 KB Output is correct
70 Correct 130 ms 52796 KB Output is correct
71 Correct 130 ms 52852 KB Output is correct
72 Correct 107 ms 52880 KB Output is correct
73 Correct 119 ms 52352 KB Output is correct
74 Correct 143 ms 52944 KB Output is correct
75 Correct 117 ms 52856 KB Output is correct
76 Correct 139 ms 58948 KB Output is correct
77 Correct 142 ms 57884 KB Output is correct
78 Correct 213 ms 58732 KB Output is correct
79 Correct 205 ms 57600 KB Output is correct
80 Correct 211 ms 62424 KB Output is correct
81 Correct 278 ms 60076 KB Output is correct
82 Correct 212 ms 59864 KB Output is correct
83 Correct 262 ms 57988 KB Output is correct
84 Correct 206 ms 61260 KB Output is correct
85 Correct 207 ms 60584 KB Output is correct
86 Correct 204 ms 57676 KB Output is correct
87 Correct 228 ms 59016 KB Output is correct
88 Correct 170 ms 59340 KB Output is correct
89 Correct 165 ms 57300 KB Output is correct
90 Correct 176 ms 57980 KB Output is correct
91 Correct 169 ms 58828 KB Output is correct
92 Correct 236 ms 57256 KB Output is correct
93 Correct 187 ms 57688 KB Output is correct
94 Correct 238 ms 57172 KB Output is correct
95 Correct 167 ms 58220 KB Output is correct
96 Correct 195 ms 56952 KB Output is correct
97 Correct 202 ms 58464 KB Output is correct