oj.uz

Submission #526710

# Submission time Handle Problem Language Result Execution time Memory
526710 2022-02-16T02:31:51 Z joelau Parkovi (COCI22_parkovi) C++14
0 / 110
 326 ms 64808 KB 
#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, lazy = 0;
        if (s != e) l = new node(s,m), r = new node(m+1,e), v = max(l->v,r->v);
        else v = dist[s];
    }
    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);
    dfs2(0,-1);
    cout << ans.first << '\n' << ans.second+1;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4940 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 62244 KB Output is correct
2 Correct 241 ms 63804 KB Output is correct
3 Correct 213 ms 48052 KB Output is correct
4 Incorrect 326 ms 46288 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 64808 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4940 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -