Submission #541451

#	Time	Username	Problem	Language	Result	Execution time	Memory
541451		eecs	Paths (RMI21_paths)	C++17	68 / 100	1092 ms	19600 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 100010;
int n, K;
ll down[maxn], up[maxn], ans[maxn];
vector<array<int, 2>> G[maxn];

namespace DS {
multiset<ll> S;

void ins(ll x) {
    S.insert(x);
}

void del(ll x) {
    S.erase(S.find(x));
}

ll query() {
    ll s = 0;
    auto it = S.rbegin();
    for (int i = 0; i < K && it != S.rend(); i++) s += *it++;
    return s;
}
} // namespace DS

int main() {
    scanf("%d %d", &n, &K);
    for (int i = 1, u, v, w; i < n; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].push_back({v, w}), G[v].push_back({u, w});
    }
    function<void(int, int)> dfs1 = [&](int u, int fa) {
        for (auto &e : G[u]) if (e[0] ^ fa) {
            dfs1(e[0], u), down[u] = max(down[u], down[e[0]] + e[1]);
        }
    };
    function<void(int, int)> dfs2 = [&](int u, int fa) {
        vector<ll> W = {0};
        for (auto &e : G[u]) if (e[0] ^ fa) {
            W.push_back(down[e[0]] + e[1]);
        }
        sort(W.begin(), W.end(), greater<>());
        for (int i = 1; i < W.size(); i++) {
            DS::ins(W[i]);
        }
        for (auto &e : G[u]) if (e[0] ^ fa) {
            up[e[0]] = max(up[u], down[e[0]] + e[1] == W[0] ? W[1] : W[0]) + e[1];
            dfs2(e[0], u);
        }
    };
    function<void(int, int)> dfs3 = [&](int u, int fa) {
        ans[u] = DS::query();
        for (auto &e : G[u]) if (e[0] ^ fa) {
            DS::ins(up[e[0]]), DS::ins(down[e[0]]);
            DS::del(up[e[0]] - e[1]), DS::del(down[e[0]] + e[1]);
            dfs3(e[0], u);
            DS::del(up[e[0]]), DS::del(down[e[0]]);
            DS::ins(up[e[0]] - e[1]), DS::ins(down[e[0]] + e[1]);
        }
    };
    dfs1(1, 0), dfs2(1, 0);
    DS::ins(down[1]), dfs3(1, 0);
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i = 1; i < W.size(); i++) {
      |                         ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d %d", &n, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d %d %d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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