oj.uz

Submission #526713

# Submission time Handle Problem Language Result Execution time Memory
526713 2022-02-16T02:45:11 Z joelau Parkovi (COCI22_parkovi) C++14
10 / 110
 420 ms 61964 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, 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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 59316 KB Output is correct
2 Correct 271 ms 60712 KB Output is correct
3 Correct 264 ms 43808 KB Output is correct
4 Correct 387 ms 42432 KB Output is correct
5 Correct 367 ms 44864 KB Output is correct
6 Correct 378 ms 44984 KB Output is correct
7 Correct 380 ms 44044 KB Output is correct
8 Correct 420 ms 44996 KB Output is correct
9 Correct 379 ms 42508 KB Output is correct
10 Correct 411 ms 46844 KB Output is correct
11 Correct 357 ms 47556 KB Output is correct
12 Correct 319 ms 46820 KB Output is correct
13 Correct 374 ms 50920 KB Output is correct
14 Correct 319 ms 45592 KB Output is correct
15 Correct 325 ms 45308 KB Output is correct
16 Correct 357 ms 47144 KB Output is correct
17 Correct 322 ms 45904 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 61964 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 3 ms 4940 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -