Submission #537551

#	Time	Username	Problem	Language	Result	Execution time	Memory
537551		joelau	Paths (RMI21_paths)	C++14	0 / 100	133 ms	26096 KiB

Main

#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) {
    dist[x] = 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;
    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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32