oj.uz

Submission #931621

# Submission time Handle Problem Language Result Execution time Memory
931621 2024-02-22T07:12:48 Z vjudge1 Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 27472 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N = 2e5 + 10, INF = 1e9;

bool mark[N], flag[N];
int n, k, C[N], ans = INF, ptr, p[N];
vector<int> G[N], vec[N];
queue<int> q;

void dfs1(int v) {
    ptr++;
    for (auto e : vec[v])
        if (!mark[e]) q.push(e);
    flag[v] = true;
}

void dfs2(int v, int par) {
    p[v] = par;
    for (auto e : G[v])
        if (e ^ par) dfs2(e, v);
}

void f(int v) {
    if (!mark[v]) {
        if (!flag[C[v]]) dfs1(C[v]);
        f(p[v]);
    }
}

int main() {
    ios:: sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    for (int i = 1; i <= n; i++) {
        int c;
        cin >> c;
        C[i] = c;
        vec[c].pb(i);
    }
    ans = k;
    for (int i = 1; i <= k; i++) {
        if (vec[i].size()) {
            mark[*vec[i].begin()] = true;
            ptr = 0, dfs1(i);
            dfs2(*vec[i].begin(), 0);
            while (!q.empty()) {
                auto u = q.front();
                q.pop(), f(u);
            }
            ans = min(ans, ptr);
            for (int j = 1; j <= n; j++) flag[j] = false;
            for (int j = 1; j <= n; j++) mark[j] = false;
        }
    }
    cout << ans - 1 << endl;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 11096 KB Output is correct
6 Correct 2 ms 10684 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 2 ms 10684 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 28 ms 10840 KB Output is correct
12 Correct 28 ms 10844 KB Output is correct
13 Correct 29 ms 10980 KB Output is correct
14 Correct 30 ms 10844 KB Output is correct
15 Correct 37 ms 10844 KB Output is correct
16 Correct 88 ms 10984 KB Output is correct
17 Correct 557 ms 10996 KB Output is correct
18 Correct 557 ms 10844 KB Output is correct
19 Correct 560 ms 11000 KB Output is correct
20 Correct 555 ms 10996 KB Output is correct
21 Correct 559 ms 10840 KB Output is correct
22 Correct 1462 ms 11280 KB Output is correct
23 Correct 1314 ms 11284 KB Output is correct
24 Correct 204 ms 10840 KB Output is correct
25 Correct 389 ms 10840 KB Output is correct
26 Correct 393 ms 11016 KB Output is correct
27 Correct 390 ms 11020 KB Output is correct
28 Correct 227 ms 10844 KB Output is correct
29 Correct 228 ms 10840 KB Output is correct
30 Correct 221 ms 11024 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3041 ms 27472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 11096 KB Output is correct
6 Correct 2 ms 10684 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 2 ms 10684 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 28 ms 10840 KB Output is correct
12 Correct 28 ms 10844 KB Output is correct
13 Correct 29 ms 10980 KB Output is correct
14 Correct 30 ms 10844 KB Output is correct
15 Correct 37 ms 10844 KB Output is correct
16 Correct 88 ms 10984 KB Output is correct
17 Correct 557 ms 10996 KB Output is correct
18 Correct 557 ms 10844 KB Output is correct
19 Correct 560 ms 11000 KB Output is correct
20 Correct 555 ms 10996 KB Output is correct
21 Correct 559 ms 10840 KB Output is correct
22 Correct 1462 ms 11280 KB Output is correct
23 Correct 1314 ms 11284 KB Output is correct
24 Correct 204 ms 10840 KB Output is correct
25 Correct 389 ms 10840 KB Output is correct
26 Correct 393 ms 11016 KB Output is correct
27 Correct 390 ms 11020 KB Output is correct
28 Correct 227 ms 10844 KB Output is correct
29 Correct 228 ms 10840 KB Output is correct
30 Correct 221 ms 11024 KB Output is correct
31 Execution timed out 3041 ms 27472 KB Time limit exceeded
32 Halted 0 ms 0 KB -