oj.uz

Submission #556590

# Submission time Handle Problem Language Result Execution time Memory
556590 2022-05-03T11:47:35 Z eecs Parkovi (COCI22_parkovi) C++17
0 / 110
 1274 ms 42068 KB 
#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]] + 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]] >= 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5008 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5004 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 31404 KB Output is correct
2 Correct 376 ms 32112 KB Output is correct
3 Correct 343 ms 15964 KB Output is correct
4 Incorrect 1274 ms 14916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 32612 KB Output is correct
2 Correct 382 ms 31836 KB Output is correct
3 Correct 345 ms 30540 KB Output is correct
4 Correct 359 ms 30404 KB Output is correct
5 Correct 427 ms 42068 KB Output is correct
6 Incorrect 404 ms 36868 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5008 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5004 KB Output isn't correct
8 Halted 0 ms 0 KB -