oj.uz

Submission #947509

# Submission time Handle Problem Language Result Execution time Memory
947509 2024-03-16T10:11:32 Z weakweakweak Capital City (JOI20_capital_city) C++17
0 / 100
 3000 ms 63252 KB 
//又抄解
#include <bits/stdc++.h>
using namespace std;

const int N = 510000;
int n, k, col[N], sz[N], parr[N], vis[N] = {0}, ans = INT_MAX, vis2[N] = {0}, tt = 3, tt2 = 5;
bool block[N] = {0}, finish[N] = {0};
vector <int> e[N], bel[N];


int dfs_sz (int i, int par) {
    sz[i] = 1;
    parr[i] = par;
    for (int j : e[i]) if (j != par and !block[j]) {
        dfs_sz (j, i);
        sz[i] += sz[j];
    }
    vis2[i] = tt;
return sz[i];}

int dfs_cen (int i, int par, int tot) {
    for (int j : e[i]) if (j != par and !block[j] and sz[j] * 2 > tot) return dfs_cen(j, i, tot);
    return i;
}

void solve (int st) {
    vector <int> color_used = {st};
    queue<int> q;
    tt2++;
    vis[st] = tt2;
    for (int j : bel[st]) q.push(j);
    while (q.size()) {
        int i = q.front(); q.pop();
        // if (vis2[i] != tt) return;
        // if (vis2[parr[i]] != tt) return;
        if (finish[col[parr[i]]]) return;
        if (vis[col[parr[i]]] != tt2) {
            vis[col[parr[i]]] = tt2;
            color_used.push_back(col[parr[i]]);
            for (int x : bel[col[parr[i]]]) q.push(x);
        }
     }
    for (int c : color_used) finish[c] = 1;
    // cout << '\n';
    // for (int x : color_used) cout << x << ' ';
    // cout << '\n';
    ans = min(ans, (int)color_used.size() - 1);
}

void CD (int i) {
    int tot = dfs_sz(i, i);
    int cen = dfs_cen(i, i, tot);
    dfs_sz(cen, cen);
    tt++;
    if (!finish[col[cen]]) solve(col[cen]);
    block[cen] = 1;
    for (int j : e[cen]) if (!block[j]) CD(j);
}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }   
    for (int i = 1; i <= n; i++) {
        cin >> col[i];
        bel[col[i]] . push_back(i);
    }

    CD(1);

    cout << ans << '\n';
return 0;}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33368 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Incorrect 7 ms 33372 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33368 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Incorrect 7 ms 33372 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33368 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Incorrect 7 ms 33372 KB Output isn't correct
5 Halted 0 ms 0 KB -