Submission #1001604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001604		Unforgettablepl	Capital City (JOI20_capital_city)	C++17	11 / 100	3051 ms	93604 KiB

capital_city

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

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin >> n >> k;
    vector<vector<int>> adj(n+1);
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    vector<int> col(n+1);
    for(int i=1;i<=n;i++)cin>>col[i];
    vector<int> nodes(k+1);
    function<void(int,int,int)> dfs = [&](int x,int par,int dep){
        nodes[col[x]] = x;
        for(int&i:adj[x])if(i!=par)dfs(i,x,dep+1);
    };
    dfs(1,0,1);
    vector<vector<int>> compoadj(k+1);
    for(int i=1;i<=k;i++){
        set<int> bad;
        function<bool(int,int)> pdfs = [&](int x,int p){
            bool found = col[x]==i;
            for(int&i:adj[x])if(i!=p)if(pdfs(i,x))found=true;
            if(found)bad.insert(col[x]);
            return found;
        };
        pdfs(nodes[i],0);
        for(int x:bad)compoadj[i].emplace_back(x);
    }
    vector<bool> visited(k+1);
    int siz = 0;
    function<void(int)> compodfs = [&](int x){
        if(visited[x])return;
        siz++;
        visited[x]=true;
        for(int&i:compoadj[x])compodfs(i);
    };
    int ans = n;
    for(int i=1;i<=k;i++){
        siz = 0;
        visited = vector<bool>(k+1);
        compodfs(i);
        ans = min(ans,siz-1);
    }
    cout << ans << '\n';
}

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