제출 #1219235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219235		arbuzick	Paths (RMI21_paths)	C++20	100 / 100	500 ms	38056 KiB

Main

#include <bits/stdc++.h>

using namespace std;

constexpr long long INF = (long long)1e18 + 7;

constexpr int R = 1 << 17;

pair<long long, int> mx[R * 2];

long long add[R * 2];

void build() {
    for (int i = R - 1; i > 0; --i) {
        mx[i] = max(mx[i * 2], mx[i * 2 + 1]);
        add[i] = 0;
    }
}

void push(int node) {
    if (add[node] != 0) {
        mx[node * 2].first += add[node];
        add[node * 2] += add[node];
        mx[node * 2 + 1].first += add[node];
        add[node * 2 + 1] += add[node];
    }
    add[node] = 0;
}

void add_to_segm(int ql, int qr, int val, int node = 1, int nl = 0, int nr = R) {
    if (ql <= nl && nr <= qr) {
        mx[node].first += val;
        add[node] += val;
        return;
    }
    if (qr <= nl || nr <= ql) {
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    add_to_segm(ql, qr, val, node * 2, nl, nm);
    add_to_segm(ql, qr, val, node * 2 + 1, nm, nr);
    mx[node] = max(mx[node * 2], mx[node * 2 + 1]);
}

constexpr int MAXN = 1e5 + 5;

vector<pair<int, int>> g[MAXN];

int pr[MAXN];

int t = 0;

int tin[MAXN], tout[MAXN];

int ord[MAXN];

long long d[MAXN];

void calc_d(int v) {
    tin[v] = t++;
    ord[tin[v]] = v;
    mx[tin[v] + R] = make_pair(d[v], tin[v]);
    for (auto [u, c] : g[v]) {
        if (u != pr[v]) {
            pr[u] = v;
            d[u] = d[v] + c;
            calc_d(u);
        }
    }
    tout[v] = t;
}

int used[MAXN], cnt_used[MAXN];

long long sum_d[MAXN];

long long mn = INF;

void calc_cnt_used(int v) {
    cnt_used[v] = used[v];
    if (used[v]) {
        sum_d[v] = d[v];
    } else {
        sum_d[v] = 0;
    }
    for (auto [u, c] : g[v]) {
        if (u != pr[v]) {
            calc_cnt_used(u);
            cnt_used[v] += cnt_used[u];
            sum_d[v] += sum_d[u];
        }
    }
    for (auto [u, c] : g[v]) {
        if (u != pr[v]) {
            if (cnt_used[u] == 1 && cnt_used[v] > 1) {
                mn = min(mn, sum_d[u] - d[v]);
            }
        }
    }
}

long long sum_up[MAXN];

long long mn_nw[MAXN];

void calc_up(int v) {
    for (auto [u, c] : g[v]) {
        if (u != pr[v]) {
            if (cnt_used[u] == 1) {
                mn_nw[v] = min(mn_nw[v], sum_d[u] - d[v]);
            }
        }
    }
    for (auto [u, c] : g[v]) {
        if (u != pr[v]) {
            if (cnt_used[u] == 0) {
                sum_up[u] = sum_up[v] + c;
            } else {
                sum_up[u] = 0;
            }
            mn_nw[u] = mn_nw[v];
            calc_up(u);
        }
    }
}

void solve() {
    int n, k;
    cin >> n >> k;
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n - 1; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        x--, y--;
        g[x].emplace_back(y, c);
        g[y].emplace_back(x, c);
        mp[make_pair(x, y)] = mp[make_pair(y, x)] = c;
    }
    t = 0;
    pr[0] = 0;
    d[0] = 0;
    calc_d(0);
    int mx1 = 0;
    for (int i = 1; i < n; ++i) {
        if (d[i] > d[mx1] || (d[i] == d[mx1] && tin[i] > tin[mx1])) {
            mx1 = i;
        }
    }
    t = 0;
    pr[mx1] = mx1;
    d[mx1] = 0;
    calc_d(mx1);
    int mx2 = 0;
    for (int i = 1; i < n; ++i) {
        if (d[i] > d[mx2] || (d[i] == d[mx2] && tin[i] > tin[mx2])) {
            mx2 = i;
        }
    }
    vector<long long> ans(n);
    for (auto root : {mx1, mx2}) {
        t = 0;
        pr[root] = root;
        d[root] = 0;
        calc_d(root);
        build();
        set<pair<int, int>> used_edges;
        for (int i = 0; i < n; ++i) {
            used[i] = 0;
        }
        ans[root] = 0;
        for (int j = 0; j < k; ++j) {
            ans[root] += mx[1].first;
            int nw = ord[mx[1].second];
            used[nw]++;
            while (nw != root) {
                if (used_edges.count(make_pair(pr[nw], nw))) {
                    break;
                }
                used_edges.insert(make_pair(pr[nw], nw));
                add_to_segm(tin[nw], tout[nw], -mp[make_pair(pr[nw], nw)]);
                nw = pr[nw];
            }
        }
        mn = INF;
        calc_cnt_used(root);
        for (auto [u, c] : g[root]) {
            if (cnt_used[u] == 1) {
                mn = min(mn, sum_d[u]);
            }
        }
        sum_up[root] = 0;
        mn_nw[root] = mn;
        calc_up(root);
        for (int i = 0; i < n; ++i) {
            if (i == root) {
                continue;
            }
            if (used[i]) {
                ans[i] = ans[root];
                continue;
            }
            ans[i] = max(ans[i], ans[root] - mn_nw[i] + sum_up[i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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