제출 #1370320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370320		sarahspeedy	수도 (JOI20_capital_city)	C++20	0 / 100	3093 ms	37408 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;

const int N = 200005;

int n, k;

vector<int> adj[N];

int color[N];

int parentArr[N];
int depthArr[N];

int tin[N], tout[N], timerDFS;

vector<int> nodesOfColor[N];

void dfs(int node, int parent){

    parentArr[node] = parent;

    tin[node] = ++timerDFS;

    for(auto child : adj[node]){

        if(child == parent) continue;

        depthArr[child] = depthArr[node] + 1;

        dfs(child, node);
    }

    tout[node] = timerDFS;
}

bool isAncestor(int u, int v){

    return tin[u] <= tin[v]
    &&
    tout[v] <= tout[u];
}

int lca(int u, int v){

    while(!isAncestor(u, v)){

        u = parentArr[u];
    }

    return u;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for(int i = 1; i < n; i++){

        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= n; i++){

        cin >> color[i];

        nodesOfColor[color[i]].push_back(i);
    }

    dfs(1, 0);

    int ans = k - 1;

    for(int c = 1; c <= k; c++){

        if(nodesOfColor[c].empty()) continue;

        int root = nodesOfColor[c][0];

        for(auto x : nodesOfColor[c]){

            root = lca(root, x);
        }

        set<int> distinct;

        queue<int> q;

        q.push(root);

        while(!q.empty()){

            int u = q.front();
            q.pop();

            distinct.insert(color[u]);

            for(auto v : adj[u]){

                if(v == parentArr[u]) continue;

                q.push(v);
            }
        }

        ans = min(ans, (int)distinct.size() - 1);
    }

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

• 서브태스크 1: 0 / 1
• 서브태스크 2: 0 / 10
• 서브태스크 3: 0 / 30
• 서브태스크 4: 0 / 59