oj.uz

Submission #827520

# Submission time Handle Problem Language Result Execution time Memory
827520 2023-08-16T14:17:42 Z Kubogi Parkovi (COCI22_parkovi) C++17
30 / 110
 890 ms 40844 KB 
// 11 ptt when ?
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)

const int maxn = 2e5+4, inf = 1e18;
int n, k;
vector<pair<int, int> > adj[maxn];

int f[maxn], g[maxn];
bool chosen[maxn];
void dfs(int u, int p, int val, int wp) {
    for (auto e: adj[u]) {
        int v = e.first, w = e.second;
        if (v != p) {
            dfs(v, u, val, w);
            f[u] = max(f[u], w + f[v]);
            g[u] = min(g[u], w + g[v]);
        }
    }
    if (f[u] + g[u] > val) {
        if (f[u] + wp > val) {
            chosen[u] = true;
            f[u] = -inf, g[u] = 0;
        }
    } else {
        f[u] = -inf;
    }
}

int cnt(int val) {
    fill(f+1, f+1+n, 0);
    fill(g+1, g+1+n, inf);
    fill(chosen+1, chosen+1+n, false);
    dfs(1, 0, val, -inf);
    chosen[1] = (g[1] > val);

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += chosen[i];
    }
    return res;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fileio("ktree");
    // freopen("debug.txt", "w", stderr);

    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    int l = 0, r = 1e15;
    while (l <= r) {
        int mid = (l+r)>>1;
        if (cnt(mid) <= k) r = mid-1;
        else l = mid+1;
    }
    cout << l << "\n";
    int x = cnt(l);
    for (int i = 1; i <= n; i++) {
        if (chosen[i]) cout << i << " ";
        else if (x < k) {
            cout << i << " ";
            x++;
        }
    }

    return 0 ^ 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:6:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:50:5: note: in expansion of macro 'fileio'
   50 |     fileio("ktree");
      |     ^~~~~~
Main.cpp:6:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:50:5: note: in expansion of macro 'fileio'
   50 |     fileio("ktree");
      |     ^~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 35564 KB Output is correct
2 Correct 349 ms 36372 KB Output is correct
3 Correct 270 ms 18564 KB Output is correct
4 Correct 866 ms 18752 KB Output is correct
5 Correct 773 ms 17968 KB Output is correct
6 Correct 755 ms 17992 KB Output is correct
7 Correct 810 ms 18000 KB Output is correct
8 Correct 890 ms 18752 KB Output is correct
9 Correct 854 ms 18372 KB Output is correct
10 Correct 835 ms 18688 KB Output is correct
11 Incorrect 679 ms 20004 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 36584 KB Output is correct
2 Correct 335 ms 39244 KB Output is correct
3 Correct 283 ms 37396 KB Output is correct
4 Correct 310 ms 37312 KB Output is correct
5 Correct 311 ms 39800 KB Output is correct
6 Correct 357 ms 39564 KB Output is correct
7 Correct 370 ms 40844 KB Output is correct
8 Correct 376 ms 39816 KB Output is correct
9 Correct 295 ms 39500 KB Output is correct
10 Correct 316 ms 38732 KB Output is correct
11 Correct 292 ms 37556 KB Output is correct
12 Correct 342 ms 40460 KB Output is correct
13 Correct 355 ms 40612 KB Output is correct
14 Correct 371 ms 39872 KB Output is correct
15 Correct 367 ms 38064 KB Output is correct
16 Correct 309 ms 36556 KB Output is correct
17 Correct 288 ms 36552 KB Output is correct
18 Correct 304 ms 38288 KB Output is correct
19 Correct 303 ms 37580 KB Output is correct
20 Correct 306 ms 38372 KB Output is correct
21 Correct 291 ms 37648 KB Output is correct

Subtask #4
0 / 60.0

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