Submission #526713

#	Time	Username	Problem	Language	Result	Execution time	Memory
526713		joelau	Parkovi (COCI22_parkovi)	C++14	10 / 110	420 ms	61964 KiB

Main

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

long long N,K, pre[200005], post[200005], dist[200005], cnt = 0, inf = 4e18;
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 dfs (long long x, long long p, long long d) {
    dist[x] = d, pre[x] = cnt++;
    for (auto v: lst[x]) if (v.first != p) dfs(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);
    }
}

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);
    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;

    return 0;
}

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