oj.uz

Submission #537556

# Submission time Handle Problem Language Result Execution time Memory
537556 2022-03-15T08:28:48 Z joelau Paths (RMI21_paths) C++14
12 / 100
 199 ms 27468 KB 
#include <bits/stdc++.h>
using namespace std;

long long N,K, p[100005][20], depth[100005], dist[100005];
vector< pair<long long,long long> > lst[100005];
pair<long long,long long> furthest;

void dfs (long long x, long long par, long long d, long long l) {
    p[x][0] = par, depth[x] = l, dist[x] = d;
    for (auto v: lst[x]) if (v.first != par) dfs(v.first, x, d+v.second,l+1);
}

void dfs2 (long long x, long long p, long long d) {
    furthest = max(furthest, make_pair(d,x));
    for (auto v: lst[x]) if (v.first != p) dfs2(v.first, x, d+v.second);
}

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;
    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);
    }
    furthest = make_pair(-1,-1);
    dfs2(0,-1,0);
    long long a = furthest.second;
    furthest = make_pair(-1,-1);
    dfs2(a,-1,0);
    long long b = furthest.second;
    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];
    }
    for (long long i = 0; i < N; ++i) cout << max(dist[i]+dist[a]-dist[lca(a,i)]*2,dist[i]+dist[b]-dist[lca(b,i)]*2) << '\n';

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 26044 KB Output is correct
2 Correct 199 ms 27468 KB Output is correct
3 Correct 147 ms 25932 KB Output is correct
4 Correct 118 ms 26036 KB Output is correct
5 Correct 175 ms 26848 KB Output is correct
6 Correct 116 ms 26048 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -