Submission #392188

#	Time	Username	Problem	Language	Result	Execution time	Memory
392188		parsabahrami	Capital City (JOI20_capital_city)	C++17	11 / 100	3078 ms	43208 KiB

capital_city

/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10, MOD = 1e9 + 7;
int ret = MOD, c, n, k, hide[N], H[N], S[N], P[N], M[N], dead[N], C[N]; vector<int> adj[N], col[N];

void preDFS(int v, int p = -1) {
    S[v] = 1;
    for (int u : adj[v])
        if (!M[u] && u != p) preDFS(u, v), S[v] += S[u];
}

int centroid(int v, int _n, int p = -1) {
    for (int u : adj[v]) {
        if (!M[u] && u != p && S[u] * 2 > _n) 
            return centroid(u, _n, v);
    }
    return v;
}

void DFS(int v, int p = -1) {
    H[v] = c, P[v] = (~p ? p : v);
    for (int u : adj[v]) {
        if (!M[u] && u != p && !dead[C[u]]) DFS(u, v);
    }
}

void decompose(int v) {
    preDFS(v); 
    v = centroid(v, S[v]);
    c = C[v];
    if (!dead[c]) {
        DFS(v);
        queue<int> Q; vector<int> hist;
        Q.push(c); 
        int now = 0, f = 1;
        while (SZ(Q)) {
            int _c = Q.front(); Q.pop();
            if (hide[_c]) continue;
            hide[_c] = 1; hist.push_back(_c);
            now++;
            for (int u : col[_c]) {
                if (H[u] != c || dead[_c]) f = 0;
                if (C[P[u]] != C[u] && !hide[C[P[u]]]) Q.push(C[P[u]]);
            }
        }
        while (SZ(hist)) {
            int u = hist.back(); hist.pop_back();
            hide[u] = 0;
        }
        dead[c] = 1;
        if (f) ret = min(ret, now - 1);
    }
    M[v] = 1;
    for (int u : adj[v])
       if (!M[u]) decompose(u);
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &C[i]); col[C[i]].push_back(i);
    }
    decompose(1);
    printf("%d\n", ret);
    return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:71:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |         scanf("%d", &C[i]); col[C[i]].push_back(i);
      |         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59