Submission #526701

#	Time	Username	Problem	Language	Result	Execution time	Memory
526701		joelau	Parkovi (COCI22_parkovi)	C++14	10 / 110	3089 ms	63860 KiB

Main

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

long long N,K, dist[200005], p[200005][20], depth[200005], inf = 2e9;
vector< pair<long long,long long> > lst[200005];

void dfs (long long x, long long par, long long d1, long long d2) {
    dist[x] = d1, depth[x] = d2, p[x][0] = par;
    for (auto v: lst[x]) if (v.first != par) dfs(v.first,x,d1+v.second,d2+1);
}

long long lca (long long a, long long b) {
    if (depth[a] < depth[b]) swap(a,b);
    for (long long k = 19; k >= 0; --k) if (p[a][k] != -1 && depth[p[a][k]] >= depth[b]) a = p[a][k];
    if (a == b) return a;
    for (long long k = 19; k >= 0; --k) if (p[a][k] != p[b][k]) a = p[a][k], b = p[b][k];
    return p[a][0];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K;
    for (long long i = 0; i < N-1; ++i) {
        long long u,v,w; cin >> u >> v >> w; u--, v--;
        lst[u].emplace_back(v,w), lst[v].emplace_back(u,w);
    }
    dfs(0,-1,0,0);
    for (long long k = 1; k < 20; ++k) for (long long i = 0; i < N; ++i) {
        if (p[i][k-1] == -1) p[i][k] = -1;
        else p[i][k] = p[p[i][k-1]][k-1];
    }
    pair<long long,long long> ans = make_pair(inf,inf);
    for (long long i = 0; i < (1<<N); ++i) if (__builtin_popcount(i) == K) {
        long long most = 0;
        for (long long u = 0; u < N; ++u) {
            long long d = inf;
            for (long long v = 0; v < N; ++v) if (i & (1<<v)) d = min(d,dist[u]+dist[v]-2*dist[lca(u,v)]);
            most = max(most,d);
        }
        ans = min(ans,make_pair(most,i));
    }
    cout << ans.first << '\n';
    for (long long k = 0; k < N; ++k) if (ans.second & (1<<k)) cout << k+1 << ' ';

    return 0;
}

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