Submission #1160752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160752		Math4Life2020	Capital City (JOI20_capital_city)	C++20	1 / 100	3096 ms	25480 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

int main() {
	ll N,K; cin >> N >> K;
    vector<ll> adj[N];
    ll radj[N];
    vector<ll> fadj[N];
    for (ll i=0;i<(N-1);i++) {
        ll a,b; cin >> a >> b; a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    radj[0]=-1;
    queue<ll> q0;
    q0.push(0);
    while (!q0.empty()) {
        ll x0 = q0.front(); q0.pop();
        for (ll y0: adj[x0]) {
            if (radj[x0]!=y0) {
                radj[y0]=x0;
                fadj[x0].push_back(y0);
                q0.push(y0);
            } 
        }
    }
    ll C[N];
    for (ll i=0;i<N;i++) {
        cin >> C[i]; C[i]--;
        assert(C[i]<K);
    }
    ll ans = 1e18;
    for (ll B=0;B<((1LL<<K));B++) {
        bool isa[K];
        for (ll i=0;i<K;i++) {
            isa[i]=(B>>i)%2;
        }
        ll nstr = 0;
        for (ll i=0;i<N;i++) {
            if (isa[C[i]]) {
                if (i==0 || !isa[C[radj[i]]]) {
                    nstr++;
                }
            }
        }
        if (nstr==1) {
            ans = min(ans,(ll)__builtin_popcount(B));
        }
    }
    cout << ans-1 << "\n";
}

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