oj.uz

Submission #556592

# Submission time Handle Problem Language Result Execution time Memory
556592 2022-05-03T11:48:23 Z eecs Parkovi (COCI22_parkovi) C++17
30 / 110
 1119 ms 47032 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]] && 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

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 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 31476 KB Output is correct
2 Correct 382 ms 32024 KB Output is correct
3 Correct 368 ms 15864 KB Output is correct
4 Incorrect 1119 ms 14940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 32624 KB Output is correct
2 Correct 359 ms 31832 KB Output is correct
3 Correct 324 ms 30460 KB Output is correct
4 Correct 333 ms 30524 KB Output is correct
5 Correct 400 ms 41960 KB Output is correct
6 Correct 398 ms 36940 KB Output is correct
7 Correct 436 ms 43372 KB Output is correct
8 Correct 364 ms 36596 KB Output is correct
9 Correct 347 ms 36260 KB Output is correct
10 Correct 350 ms 35660 KB Output is correct
11 Correct 336 ms 34440 KB Output is correct
12 Correct 462 ms 47032 KB Output is correct
13 Correct 440 ms 44504 KB Output is correct
14 Correct 435 ms 41028 KB Output is correct
15 Correct 369 ms 34908 KB Output is correct
16 Correct 324 ms 33556 KB Output is correct
17 Correct 352 ms 33484 KB Output is correct
18 Correct 343 ms 35176 KB Output is correct
19 Correct 398 ms 43304 KB Output is correct
20 Correct 386 ms 42320 KB Output is correct
21 Correct 365 ms 39744 KB Output is correct

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 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -