Submission #526760

#	Time	Username	Problem	Language	Result	Execution time	Memory
526760		joelau	Parkovi (COCI22_parkovi)	C++14	50 / 110	1456 ms	62532 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60