oj.uz

Submission #928341

# Submission time Handle Problem Language Result Execution time Memory
928341 2024-02-16T08:45:20 Z Amirreza_Fakhri Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 38696 KB 
// In the name of the God
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e5+5;

int n, k, c[maxn], sz[maxn], par[maxn], id[maxn];
bool mark[maxn], vis[maxn];
vector <int> adj[maxn], vec[maxn];
queue <int> q;

void dfs1(int v, int p) {
    sz[v] = 1;
    vis[c[v]] = 1;
    for (int u : adj[v]) {
        if (!mark[u] and u != p) {
            dfs1(u, v); sz[v] += sz[u];
        }
    }
}

void dfs2(int v, int p, int r) {
    par[v] = p, id[v] = r;
    for (int u : adj[v]) {
        if (!mark[u] and u != p) dfs2(u, v, r);
    }
}

int fcen(int v, int p, int s) {
    for (int u : adj[v]) {
        if (!mark[u] and u != p and sz[u]*2 > sz[v]) return fcen(u, v, s);
    }
    return v;
}

int cen(int v) {
    dfs1(v, v);
    v = fcen(v, v, sz[v]);
    dfs2(v, v, v); 
    int ans = 0;
    q.push(c[v]);
    while (q.size()) {
        int col = q.front(); q.pop();
        if (!vis[col]) continue;
        vis[col] = 0;
        for (int u : vec[col]) {
            if (id[u] != v) {
                ans = k; break;
            }
            q.push(c[par[u]]);
        }
        ans++;
    }
    mark[v] = 1;
    for (int u : adj[v]) {
        if (!mark[u]) smin(ans, cen(u));
    }
    return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int v, u; cin >> v >> u;
        adj[--v].pb(--u);
        adj[u].pb(v);
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i]; vec[--c[i]].pb(i);
    }
    cout << cen(0)-1 << '\n';
    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12924 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 4 ms 12948 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 4 ms 12892 KB Output is correct
13 Correct 6 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 6 ms 12956 KB Output is correct
16 Correct 4 ms 12888 KB Output is correct
17 Correct 9 ms 12892 KB Output is correct
18 Correct 9 ms 12892 KB Output is correct
19 Correct 9 ms 12888 KB Output is correct
20 Correct 10 ms 12892 KB Output is correct
21 Correct 9 ms 12892 KB Output is correct
22 Correct 25 ms 13200 KB Output is correct
23 Correct 33 ms 13144 KB Output is correct
24 Correct 8 ms 12892 KB Output is correct
25 Correct 36 ms 13196 KB Output is correct
26 Correct 37 ms 13144 KB Output is correct
27 Correct 36 ms 13148 KB Output is correct
28 Correct 21 ms 13148 KB Output is correct
29 Correct 22 ms 13144 KB Output is correct
30 Correct 22 ms 13148 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12924 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 4 ms 12948 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 4 ms 12892 KB Output is correct
13 Correct 6 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 6 ms 12956 KB Output is correct
16 Correct 4 ms 12888 KB Output is correct
17 Correct 9 ms 12892 KB Output is correct
18 Correct 9 ms 12892 KB Output is correct
19 Correct 9 ms 12888 KB Output is correct
20 Correct 10 ms 12892 KB Output is correct
21 Correct 9 ms 12892 KB Output is correct
22 Correct 25 ms 13200 KB Output is correct
23 Correct 33 ms 13144 KB Output is correct
24 Correct 8 ms 12892 KB Output is correct
25 Correct 36 ms 13196 KB Output is correct
26 Correct 37 ms 13144 KB Output is correct
27 Correct 36 ms 13148 KB Output is correct
28 Correct 21 ms 13148 KB Output is correct
29 Correct 22 ms 13144 KB Output is correct
30 Correct 22 ms 13148 KB Output is correct
31 Execution timed out 3073 ms 38696 KB Time limit exceeded
32 Halted 0 ms 0 KB -