oj.uz

Submission #556586

# Submission time Handle Problem Language Result Execution time Memory
556586 2022-05-03T11:46:03 Z eecs Parkovi (COCI22_parkovi) C++17
0 / 110
 1218 ms 37612 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);
    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 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: In function 'int main()':
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 Incorrect 3 ms 5012 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 31324 KB Output is correct
2 Correct 397 ms 36436 KB Output is correct
3 Correct 384 ms 20396 KB Output is correct
4 Incorrect 1218 ms 19148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 32604 KB Output is correct
2 Correct 373 ms 36068 KB Output is correct
3 Correct 336 ms 34508 KB Output is correct
4 Correct 352 ms 34380 KB Output is correct
5 Correct 421 ms 37612 KB Output is correct
6 Incorrect 401 ms 37060 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 Incorrect 3 ms 5012 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -