oj.uz

Submission #540619

# Submission time Handle Problem Language Result Execution time Memory
540619 2022-03-21T08:50:35 Z AlperenT Parkovi (COCI22_parkovi) C++17
30 / 110
 2039 ms 40804 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const long long INF = 2e18 + 5;

int n, k, a, b, c;

long long l, r, m, park[N], nongood[N];

bool ispark[N];

vector<pair<int, long long>> tree[N];

void dfs(int v, int p, int pw, long long x){
    if(tree[v].size() == 1) nongood[v] = 0;

    for(auto e : tree[v]){
        if(e.first != p){
            dfs(e.first, v, e.second, x);

            park[v] = min(park[v], park[e.first] + e.second);
        }
    }

    for(auto e : tree[v]){
        if(e.first != p){
            if(nongood[e.first] + e.second + park[v] > x){
                nongood[v] = max(nongood[v], nongood[e.first] + e.second);
            }
        }
    }

    if(park[v] > x) nongood[v] = max(nongood[v], 0ll);

    if(nongood[v] + pw > x) ispark[v] = true, park[v] = 0, nongood[v] = -INF;
}

bool check(long long x){
    memset(ispark, 0, sizeof(ispark)), fill(park, park + N, INF), fill(nongood, nongood + N, -INF);

    dfs(1, 0, 0, x);

    if(park[1] > x) ispark[1] = true;

    return accumulate(ispark + 1, ispark + n + 1, 0) <= k;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> k;

    for(int i = 1; i <= n - 1; i++){
        cin >> a >> b >> c;

        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }

    l = -1, r = INF;

    while(r - l > 1){
        m = l + (r - l) / 2;

        if(check(m)) r = m;
        else l = m;
    }

    check(r);

    vector<int> v;

    for(int i = 1; i <= n; i++) if(ispark[i]) v.push_back(i);

    for(int i = 1; i <= n; i++) if(!ispark[i] && v.size() < k) v.push_back(i);

    cout << r << "\n";

    for(auto i : v) cout << i << " ";
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:77:59: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |     for(int i = 1; i <= n; i++) if(!ispark[i] && v.size() < k) v.push_back(i);
      |                                                  ~~~~~~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8248 KB Output is correct
2 Correct 16 ms 8216 KB Output is correct
3 Correct 19 ms 8276 KB Output is correct
4 Correct 17 ms 8276 KB Output is correct
5 Correct 13 ms 8276 KB Output is correct
6 Correct 14 ms 8276 KB Output is correct
7 Incorrect 14 ms 8340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 37736 KB Output is correct
2 Correct 541 ms 38476 KB Output is correct
3 Correct 501 ms 17620 KB Output is correct
4 Correct 1727 ms 17932 KB Output is correct
5 Correct 1589 ms 17624 KB Output is correct
6 Correct 1705 ms 17640 KB Output is correct
7 Correct 1886 ms 17712 KB Output is correct
8 Correct 2039 ms 18216 KB Output is correct
9 Correct 1668 ms 18020 KB Output is correct
10 Correct 1781 ms 18292 KB Output is correct
11 Incorrect 1137 ms 19780 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 575 ms 39008 KB Output is correct
2 Correct 544 ms 38156 KB Output is correct
3 Correct 502 ms 36712 KB Output is correct
4 Correct 569 ms 36684 KB Output is correct
5 Correct 544 ms 39648 KB Output is correct
6 Correct 569 ms 38992 KB Output is correct
7 Correct 590 ms 40172 KB Output is correct
8 Correct 582 ms 39204 KB Output is correct
9 Correct 559 ms 38940 KB Output is correct
10 Correct 543 ms 38348 KB Output is correct
11 Correct 535 ms 37200 KB Output is correct
12 Correct 581 ms 40804 KB Output is correct
13 Correct 600 ms 40800 KB Output is correct
14 Correct 591 ms 39832 KB Output is correct
15 Correct 536 ms 38216 KB Output is correct
16 Correct 509 ms 37072 KB Output is correct
17 Correct 504 ms 36976 KB Output is correct
18 Correct 544 ms 38604 KB Output is correct
19 Correct 530 ms 38684 KB Output is correct
20 Correct 533 ms 39404 KB Output is correct
21 Correct 523 ms 38556 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8248 KB Output is correct
2 Correct 16 ms 8216 KB Output is correct
3 Correct 19 ms 8276 KB Output is correct
4 Correct 17 ms 8276 KB Output is correct
5 Correct 13 ms 8276 KB Output is correct
6 Correct 14 ms 8276 KB Output is correct
7 Incorrect 14 ms 8340 KB Output isn't correct
8 Halted 0 ms 0 KB -