oj.uz

Submission #526701

# Submission time Handle Problem Language Result Execution time Memory
526701 2022-02-16T02:18:06 Z joelau Parkovi (COCI22_parkovi) C++14
10 / 110
 3000 ms 63860 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 8 ms 4940 KB Output is correct
3 Correct 11 ms 5000 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 146 ms 4940 KB Output is correct
7 Correct 151 ms 4940 KB Output is correct
8 Correct 39 ms 4940 KB Output is correct
9 Correct 896 ms 5012 KB Output is correct
10 Correct 42 ms 4940 KB Output is correct
11 Correct 422 ms 5020 KB Output is correct
12 Correct 1034 ms 5012 KB Output is correct
13 Correct 15 ms 5000 KB Output is correct
14 Correct 395 ms 5020 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3027 ms 60444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3089 ms 63860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 8 ms 4940 KB Output is correct
3 Correct 11 ms 5000 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 146 ms 4940 KB Output is correct
7 Correct 151 ms 4940 KB Output is correct
8 Correct 39 ms 4940 KB Output is correct
9 Correct 896 ms 5012 KB Output is correct
10 Correct 42 ms 4940 KB Output is correct
11 Correct 422 ms 5020 KB Output is correct
12 Correct 1034 ms 5012 KB Output is correct
13 Correct 15 ms 5000 KB Output is correct
14 Correct 395 ms 5020 KB Output is correct
15 Execution timed out 3027 ms 60444 KB Time limit exceeded
16 Halted 0 ms 0 KB -