Submission #556592

#	Time	Username	Problem	Language	Result	Execution time	Memory
556592		eecs	Parkovi (COCI22_parkovi)	C++17	30 / 110	1119 ms	47032 KiB

Main

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

typedef long long ll;
const int maxn = 200010;
int n, K;
ll f[maxn], g[maxn];
vector<int> res;
vector<array<int, 2>> G[maxn];

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});
    }
    auto init = [&](auto self, int u, int fa) -> void {
        for (int i = 0; i < G[u].size(); i++) {
            if (G[u][i][0] == fa) { G[u].erase(G[u].begin() + i); break; }
        }
        for (auto &e : G[u]) {
            self(self, e[0], u);
        }
    };
    init(init, 1, 0);
    auto chk = [&](ll lim) {
        auto dfs = [&](auto self, int u) -> void {
            g[u] = 1e18;
            for (auto &e : G[u]) {
                self(self, e[0]);
                if (~f[e[0]] && f[e[0]] + e[1] > lim) res.push_back(e[0]), f[e[0]] = -1, g[e[0]] = 0;
                g[u] = min(g[u], g[e[0]] + e[1]);
            }
            f[u] = g[u] <= lim ? -1 : 0;
            for (auto &e : G[u]) {
                if (~f[e[0]] && f[e[0]] + g[u] > lim) f[u] = max(f[u], f[e[0]] + e[1]);
            }
        };
        res.clear(), dfs(dfs, 1);
        if (f[1] >= 0) res.push_back(1);
        return res.size() <= K;
    };
    ll l = 0, r = 1e15, ans;
    while (l <= r) {
        ll mid = (l + r) / 2;
        chk(mid) ? r = (ans = mid) - 1 : l = mid + 1;
    }
    printf("%lld\n", ans), chk(ans);
    set<int> S(res.begin(), res.end());
    for (int i = 1; i <= n; i++) {
        if (res.size() < K && !S.count(i)) res.push_back(i);
    }
    for (int x : res) printf("%d ", x);
    return 0;
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for (int i = 0; i < G[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp: In lambda function:
Main.cpp:41:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |         return res.size() <= K;
      |                ~~~~~~~~~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:51:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |         if (res.size() < K && !S.count(i)) res.push_back(i);
      |             ~~~~~~~~~~~^~~
Main.cpp: In instantiation of 'main()::<lambda(auto:23, int, int)> [with auto:23 = main()::<lambda(auto:23, int, int)>]':
Main.cpp:25:20:   required from here
Main.cpp:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for (int i = 0; i < G[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %d", &n, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d %d %d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:43:25: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |     ll l = 0, r = 1e15, ans;
      |                         ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60