Submission #541457

#	Time	Username	Problem	Language	Result	Execution time	Memory
541457		eecs	Paths (RMI21_paths)	C++17	100 / 100	440 ms	21624 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 {
ll sum;
multiset<ll> S, cand;

void ins(ll x) {
    if (S.size() < K || *S.begin() < x) {
        if (S.size() == K) sum -= *S.begin(), cand.insert(*S.begin()), S.erase(S.begin());
        sum += x, S.insert(x);
    } else {
        cand.insert(x);
    }
}

void del(ll x) {
    if (cand.find(x) != cand.end()) {
        cand.erase(cand.find(x));
    } else {
        sum -= x, S.erase(S.find(x));
        if (S.size() < K) sum += *cand.rbegin(), S.insert(*cand.rbegin()), cand.erase(prev(cand.end()));
    }
}
} // 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::sum;
        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 function 'void DS::ins(ll)':
Main.cpp:15:18: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     if (S.size() < K || *S.begin() < x) {
      |         ~~~~~~~~~^~~
Main.cpp:16:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |         if (S.size() == K) sum -= *S.begin(), cand.insert(*S.begin()), S.erase(S.begin());
      |             ~~~~~~~~~^~~~
Main.cpp: In function 'void DS::del(ll)':
Main.cpp:28:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |         if (S.size() < K) sum += *cand.rbegin(), S.insert(*cand.rbegin()), cand.erase(prev(cand.end()));
      |             ~~~~~~~~~^~~
Main.cpp: In lambda function:
Main.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int i = 1; i < W.size(); i++) {
      |                         ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d %d", &n, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         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: 32 / 32