oj.uz

Submission #526715

# Submission time Handle Problem Language Result Execution time Memory
526715 2022-02-16T02:47:46 Z joelau Parkovi (COCI22_parkovi) C++14
20 / 110
 3000 ms 60680 KB 
#include <bits/stdc++.h>
using namespace std;

long long N,K, pre[200005], post[200005], dist[200005], cnt = 0, inf = 4e18, p[200005][20], depth[200005];
vector< pair<long long,long long> > lst[200005];
pair<long long,long long> ans = make_pair(inf,inf);

struct node {
    long long s,e,m,v,lazy; node *l, *r;
    node (long long S, long long E) {
        s = S, e = E, m = (s+e)/2, v = 0, lazy = 0;
        if (s != e) l = new node(s,m), r = new node(m+1,e);
    }
    void propo() {
        if (lazy == 0) return;
        v += lazy;
        if (s != e) l->lazy += lazy, r->lazy += lazy;
        lazy = 0;
    }
    void update (long long x, long long y, long long nv) {
        propo();
        if (s == x && e == y) lazy += nv;
        else {
            if (y <= m) l -> update(x,y,nv);
            else if (x > m) r -> update(x,y,nv);
            else l -> update(x,m,nv), r -> update(m+1,y,nv);
            l->propo(), r->propo();
            v = max(l->v,r->v);
        }
    }
    long long query (long long x, long long y) {
        propo();
        if (s == x && e == y) return v;
        else if (y <= m) return l -> query(x,y);
        else if (x > m) return r -> query(x,y);
        else return max(l->query(x,m),r->query(m+1,y));
    }
}*root;

void dfs1 (long long x, long long p, long long d) {
    dist[x] = d, pre[x] = cnt++;
    for (auto v: lst[x]) if (v.first != p) dfs1(v.first,x,d+v.second);
    post[x] = cnt-1;
}

void dfs2 (long long x, long long p) {
    ans = min(ans,make_pair(root->query(0,N-1),x));
    for (auto v: lst[x]) if (v.first != p) {
        root -> update(0,N-1,v.second);
        root -> update(pre[v.first],post[v.first],-v.second*2);
        dfs2(v.first,x);
        root -> update(pre[v.first],post[v.first],v.second*2);
        root -> update(0,N-1,-v.second);
    }
}

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);
    }
    if (K == 1) {
        dfs1(0,-1,0);
        root = new node(0,N-1);
        for (long long i = 0; i < N; ++i) root -> update(pre[i],pre[i],dist[i]);
        dfs2(0,-1);
        cout << ans.first << '\n' << ans.second+1;
    }
    else {
        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 9 ms 4940 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 149 ms 4940 KB Output is correct
7 Correct 209 ms 4940 KB Output is correct
8 Correct 41 ms 4940 KB Output is correct
9 Correct 1012 ms 5008 KB Output is correct
10 Correct 47 ms 5012 KB Output is correct
11 Correct 474 ms 5008 KB Output is correct
12 Correct 1109 ms 5008 KB Output is correct
13 Correct 12 ms 4940 KB Output is correct
14 Correct 457 ms 5012 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 59316 KB Output is correct
2 Correct 289 ms 60680 KB Output is correct
3 Correct 259 ms 43780 KB Output is correct
4 Correct 394 ms 42436 KB Output is correct
5 Correct 474 ms 41372 KB Output is correct
6 Correct 381 ms 41304 KB Output is correct
7 Correct 402 ms 41540 KB Output is correct
8 Correct 375 ms 43460 KB Output is correct
9 Correct 385 ms 42524 KB Output is correct
10 Correct 475 ms 43428 KB Output is correct
11 Correct 350 ms 44300 KB Output is correct
12 Correct 329 ms 43368 KB Output is correct
13 Correct 440 ms 47092 KB Output is correct
14 Correct 346 ms 43196 KB Output is correct
15 Correct 316 ms 42660 KB Output is correct
16 Correct 361 ms 43960 KB Output is correct
17 Correct 339 ms 42764 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 60184 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 9 ms 4940 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 149 ms 4940 KB Output is correct
7 Correct 209 ms 4940 KB Output is correct
8 Correct 41 ms 4940 KB Output is correct
9 Correct 1012 ms 5008 KB Output is correct
10 Correct 47 ms 5012 KB Output is correct
11 Correct 474 ms 5008 KB Output is correct
12 Correct 1109 ms 5008 KB Output is correct
13 Correct 12 ms 4940 KB Output is correct
14 Correct 457 ms 5012 KB Output is correct
15 Correct 248 ms 59316 KB Output is correct
16 Correct 289 ms 60680 KB Output is correct
17 Correct 259 ms 43780 KB Output is correct
18 Correct 394 ms 42436 KB Output is correct
19 Correct 474 ms 41372 KB Output is correct
20 Correct 381 ms 41304 KB Output is correct
21 Correct 402 ms 41540 KB Output is correct
22 Correct 375 ms 43460 KB Output is correct
23 Correct 385 ms 42524 KB Output is correct
24 Correct 475 ms 43428 KB Output is correct
25 Correct 350 ms 44300 KB Output is correct
26 Correct 329 ms 43368 KB Output is correct
27 Correct 440 ms 47092 KB Output is correct
28 Correct 346 ms 43196 KB Output is correct
29 Correct 316 ms 42660 KB Output is correct
30 Correct 361 ms 43960 KB Output is correct
31 Correct 339 ms 42764 KB Output is correct
32 Execution timed out 3078 ms 60184 KB Time limit exceeded
33 Halted 0 ms 0 KB -