oj.uz

Submission #526760

# Submission time Handle Problem Language Result Execution time Memory
526760 2022-02-16T04:07:31 Z joelau Parkovi (COCI22_parkovi) C++14
50 / 110
 1456 ms 62532 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], A[200005];
vector< pair<long long,long long> > lst[200005];
pair<long long,long long> ans = make_pair(inf,inf);
bitset<200005> bs;

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;
    A[0] = 0;
    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);
        A[i+1] = A[i] + 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 if (N <= 20) {
        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 << ' ';
    }
    else {
        long long low = -1, high = 200000000000000;
        while (high-low > 1) {
            long long mid = (low+high)/2, n = 0;
            while (n < N && A[n] <= mid) n++;
            long long num = 1;
            while (A[N-1]-A[n-1] > mid) {
                long long a = n;
                while (a < N && A[a]-A[n-1] <= mid) a++;
                long long b = a;
                while (b < N && A[b]-A[a] <= mid) b++;
                num++, n = b;
            }
            if (num <= K) high = mid;
            else low = mid;
        }
        cout << high << '\n';
        long long n = 0;
        while (n < N && A[n] <= high) n++;
        bs[n-1] = 1;
        while (A[N-1]-A[n-1] > high) {
            long long a = n;
            while (a < N && A[a]-A[n-1] <= high) a++;
            long long b = a;
            while (b < N && A[b]-A[a] <= high) b++;
            bs[b-1] = 1, n = b;
        }
        for (long long i = 0; i < N && bs.count() < K; ++i) if (!bs[i]) bs[i] = 1;
        for (long long i = 0; i < N; ++i) if (bs[i]) cout << i+1 << ' ';
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:133:51: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  133 |         for (long long i = 0; i < N && bs.count() < K; ++i) if (!bs[i]) bs[i] = 1;
      |                                        ~~~~~~~~~~~^~~

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 5044 KB Output is correct
3 Correct 8 ms 5040 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 150 ms 5016 KB Output is correct
7 Correct 150 ms 5028 KB Output is correct
8 Correct 39 ms 4940 KB Output is correct
9 Correct 879 ms 5024 KB Output is correct
10 Correct 40 ms 5028 KB Output is correct
11 Correct 411 ms 5028 KB Output is correct
12 Correct 993 ms 5132 KB Output is correct
13 Correct 11 ms 4940 KB Output is correct
14 Correct 387 ms 5024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 60868 KB Output is correct
2 Correct 254 ms 62192 KB Output is correct
3 Correct 275 ms 45388 KB Output is correct
4 Correct 378 ms 45752 KB Output is correct
5 Correct 374 ms 44592 KB Output is correct
6 Correct 377 ms 44584 KB Output is correct
7 Correct 362 ms 44940 KB Output is correct
8 Correct 373 ms 46336 KB Output is correct
9 Correct 371 ms 43984 KB Output is correct
10 Correct 409 ms 46956 KB Output is correct
11 Correct 341 ms 47720 KB Output is correct
12 Correct 320 ms 46772 KB Output is correct
13 Correct 387 ms 50500 KB Output is correct
14 Correct 313 ms 46424 KB Output is correct
15 Correct 318 ms 45988 KB Output is correct
16 Correct 331 ms 47300 KB Output is correct
17 Correct 330 ms 46092 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 15684 KB Output is correct
2 Correct 71 ms 15424 KB Output is correct
3 Correct 66 ms 14864 KB Output is correct
4 Correct 248 ms 58704 KB Output is correct
5 Correct 101 ms 16428 KB Output is correct
6 Correct 106 ms 15908 KB Output is correct
7 Correct 110 ms 16412 KB Output is correct
8 Correct 67 ms 15792 KB Output is correct
9 Correct 66 ms 15720 KB Output is correct
10 Correct 65 ms 15396 KB Output is correct
11 Correct 237 ms 59888 KB Output is correct
12 Correct 1456 ms 16796 KB Output is correct
13 Correct 130 ms 16652 KB Output is correct
14 Correct 109 ms 16308 KB Output is correct
15 Correct 60 ms 15428 KB Output is correct
16 Correct 57 ms 15076 KB Output is correct
17 Correct 56 ms 14916 KB Output is correct
18 Correct 245 ms 62532 KB Output is correct
19 Correct 1333 ms 16136 KB Output is correct
20 Correct 101 ms 16160 KB Output is correct
21 Correct 148 ms 15924 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 8 ms 5044 KB Output is correct
3 Correct 8 ms 5040 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 150 ms 5016 KB Output is correct
7 Correct 150 ms 5028 KB Output is correct
8 Correct 39 ms 4940 KB Output is correct
9 Correct 879 ms 5024 KB Output is correct
10 Correct 40 ms 5028 KB Output is correct
11 Correct 411 ms 5028 KB Output is correct
12 Correct 993 ms 5132 KB Output is correct
13 Correct 11 ms 4940 KB Output is correct
14 Correct 387 ms 5024 KB Output is correct
15 Correct 244 ms 60868 KB Output is correct
16 Correct 254 ms 62192 KB Output is correct
17 Correct 275 ms 45388 KB Output is correct
18 Correct 378 ms 45752 KB Output is correct
19 Correct 374 ms 44592 KB Output is correct
20 Correct 377 ms 44584 KB Output is correct
21 Correct 362 ms 44940 KB Output is correct
22 Correct 373 ms 46336 KB Output is correct
23 Correct 371 ms 43984 KB Output is correct
24 Correct 409 ms 46956 KB Output is correct
25 Correct 341 ms 47720 KB Output is correct
26 Correct 320 ms 46772 KB Output is correct
27 Correct 387 ms 50500 KB Output is correct
28 Correct 313 ms 46424 KB Output is correct
29 Correct 318 ms 45988 KB Output is correct
30 Correct 331 ms 47300 KB Output is correct
31 Correct 330 ms 46092 KB Output is correct
32 Correct 74 ms 15684 KB Output is correct
33 Correct 71 ms 15424 KB Output is correct
34 Correct 66 ms 14864 KB Output is correct
35 Correct 248 ms 58704 KB Output is correct
36 Correct 101 ms 16428 KB Output is correct
37 Correct 106 ms 15908 KB Output is correct
38 Correct 110 ms 16412 KB Output is correct
39 Correct 67 ms 15792 KB Output is correct
40 Correct 66 ms 15720 KB Output is correct
41 Correct 65 ms 15396 KB Output is correct
42 Correct 237 ms 59888 KB Output is correct
43 Correct 1456 ms 16796 KB Output is correct
44 Correct 130 ms 16652 KB Output is correct
45 Correct 109 ms 16308 KB Output is correct
46 Correct 60 ms 15428 KB Output is correct
47 Correct 57 ms 15076 KB Output is correct
48 Correct 56 ms 14916 KB Output is correct
49 Correct 245 ms 62532 KB Output is correct
50 Correct 1333 ms 16136 KB Output is correct
51 Correct 101 ms 16160 KB Output is correct
52 Correct 148 ms 15924 KB Output is correct
53 Incorrect 104 ms 15940 KB Output isn't correct
54 Halted 0 ms 0 KB -