oj.uz

Submission #527706

# Submission time Handle Problem Language Result Execution time Memory
527706 2022-02-18T04:25:46 Z joelau Parkovi (COCI22_parkovi) C++14
30 / 110
 1361 ms 37236 KB 
#include <bits/stdc++.h>
using namespace std;

long long N,K, dp1[200005], dp2[200005], val, inf = 1e18;
vector< pair<long long,long long> > lst[200005];
bitset<200005> ans;

void dfs (long long x, long long p) {
    dp1[x] = inf, dp2[x] = 0;
    for (auto v: lst[x]) if (v.first != p) {
        dfs(v.first,x);
        dp1[x] = min(dp1[x],dp1[v.first] + v.second);
        if (dp2[v.first] != -1) {
            if (dp2[v.first] + v.second > val) ans[v.first] = 1, dp1[x] = min(dp1[x],v.second);
            else dp2[x] = max(dp2[x],dp2[v.first] + v.second);
        }
    }
    if (dp1[x] <= val) dp2[x] = -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K;
    for (long long i = 0; i < N-1; ++i) {
        long long u,v,w; cin >> u >> v >> w; u--, v--;
        lst[u].emplace_back(v,w), lst[v].emplace_back(u,w);
    }
    long long low = -1, high = 2e14;
    while (high - low > 1) {
        val = (low+high)/2;
        ans.reset();
        dfs(0,-1);
        if (dp2[0] != -1 && dp1[0]+dp2[0] > val) ans[0] = 1;
        if (ans.count() > K) low = val;
        else high = val;
    }
    cout << high << '\n';
    val = high;
    ans.reset();
    dfs(0,-1);
    if (dp2[0] != -1 && dp1[0]+dp2[0] > val) ans[0] = 1;
    for (long long i = 0, num = ans.count(); i < N && num < K; ++i) if (!ans[i]) ans[i] = 1, num++;
    for (long long i = 0; i < N; ++i) if (ans[i]) cout << i+1 << ' ';

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:34:25: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   34 |         if (ans.count() > K) low = val;
      |             ~~~~~~~~~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Incorrect 3 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 306 ms 34056 KB Output is correct
2 Correct 313 ms 34328 KB Output is correct
3 Correct 299 ms 21608 KB Output is correct
4 Incorrect 1361 ms 21440 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 324 ms 36228 KB Output is correct
2 Correct 322 ms 35944 KB Output is correct
3 Correct 296 ms 34180 KB Output is correct
4 Correct 322 ms 34092 KB Output is correct
5 Correct 328 ms 36380 KB Output is correct
6 Correct 393 ms 36124 KB Output is correct
7 Correct 376 ms 37236 KB Output is correct
8 Correct 317 ms 36280 KB Output is correct
9 Correct 337 ms 36004 KB Output is correct
10 Correct 311 ms 33356 KB Output is correct
11 Correct 295 ms 31016 KB Output is correct
12 Correct 383 ms 33560 KB Output is correct
13 Correct 370 ms 33684 KB Output is correct
14 Correct 342 ms 32976 KB Output is correct
15 Correct 324 ms 32000 KB Output is correct
16 Correct 333 ms 31000 KB Output is correct
17 Correct 305 ms 30796 KB Output is correct
18 Correct 320 ms 32208 KB Output is correct
19 Correct 330 ms 31700 KB Output is correct
20 Correct 358 ms 32384 KB Output is correct
21 Correct 317 ms 31752 KB Output is correct

Subtask #4
0 / 60.0

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