Submission #1224489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224489		BlockOG	Paths (RMI21_paths)	C++20	12 / 100	367 ms	30116 KiB

Main

#include <bits/stdc++.h>

// mrrrow meeow :3
// vivid/stasis! free on steam go play

using namespace std;

vector<pair<int, int>> adj[100000];
int par[100000][17];
long long dpar[100000][17];
int depth[100000];
int n, k;

void get_pars(int i, int p=-1, int d=0) {
    depth[i] = d;
    for (pair<int, int> j : adj[i]) {
        if (j.first == p) continue;
        par[j.first][0] = i;
        dpar[j.first][0] = j.second;
        get_pars(j.first, i, d + 1);
    }
}

int get_par(int i, int d) {
    for (int j = 0; j < 17; j++, d /= 2) {
        if (d & 1) i = par[i][j];
    }
    
    return i;
}

long long get_distance(int i, int d) {
    long long res = 0;
    for (int j = 0; j < 17; j++, d /= 2) {
        if (d & 1) res += dpar[i][j], i = par[i][j];
    }
    
    return res;
}

pair<long long, int> furthest(int i, int p=-1, long long d=0) {
    pair<long long, int> res = { d, i };
    for (pair<int, int> j : adj[i]) {
        if (j.first == p) continue;
        res = max(res, furthest(j.first, i, d + j.second));
    }
    
    return res;
}

long long distance(int a, int b) {
    long long res;
    if (depth[a] > depth[b]) res = get_distance(a, depth[a] - depth[b]), a = get_par(a, depth[a] - depth[b]);
    else res = get_distance(b, depth[b] - depth[a]), b = get_par(b, depth[b] - depth[a]);
    
    int l = 0, r = n;
    while (l < r) {
        int mid = (l + r) / 2;
        if (get_par(a, mid) == get_par(b, mid)) r = mid;
        else l = mid + 1;
    }
    
    return res + get_distance(a, l) + get_distance(b, l);
}

int main() {
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int a, b, c; cin >> a >> b >> c; a--, b--;
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }
    
    get_pars(0);
    for (int j = 1; j < 17; j++) {
        for (int i = 0; i < n; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
            dpar[i][j] = dpar[i][j - 1] + dpar[par[i][j - 1]][j - 1];
        }
    }
    
    int fa = furthest(0).second;
    int fb = furthest(fa).second;
    
    for (int i = 0; i < n; i++) cout << max(distance(i, fa), distance(i, fb)) << endl;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32