oj.uz

Submission #540614

# Submission time Handle Problem Language Result Execution time Memory
540614 2022-03-21T08:39:55 Z AlperenT Parkovi (COCI22_parkovi) C++17
30 / 110
 1734 ms 44664 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 = 0, 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 21 ms 8408 KB Output is correct
2 Correct 17 ms 8236 KB Output is correct
3 Correct 20 ms 8276 KB Output is correct
4 Correct 16 ms 8276 KB Output is correct
5 Correct 17 ms 8336 KB Output is correct
6 Correct 17 ms 8276 KB Output is correct
7 Incorrect 16 ms 8276 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 40520 KB Output is correct
2 Correct 571 ms 42760 KB Output is correct
3 Correct 471 ms 22268 KB Output is correct
4 Correct 1667 ms 22104 KB Output is correct
5 Correct 1613 ms 21628 KB Output is correct
6 Correct 1615 ms 21680 KB Output is correct
7 Correct 1633 ms 20512 KB Output is correct
8 Correct 1727 ms 21124 KB Output is correct
9 Correct 1628 ms 21500 KB Output is correct
10 Correct 1734 ms 21816 KB Output is correct
11 Incorrect 1112 ms 24104 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 566 ms 43384 KB Output is correct
2 Correct 545 ms 42404 KB Output is correct
3 Correct 511 ms 40644 KB Output is correct
4 Correct 502 ms 40572 KB Output is correct
5 Correct 557 ms 43804 KB Output is correct
6 Correct 560 ms 43248 KB Output is correct
7 Correct 591 ms 44664 KB Output is correct
8 Correct 563 ms 42932 KB Output is correct
9 Correct 560 ms 42700 KB Output is correct
10 Correct 526 ms 41888 KB Output is correct
11 Correct 532 ms 40688 KB Output is correct
12 Correct 590 ms 44368 KB Output is correct
13 Correct 601 ms 44436 KB Output is correct
14 Correct 587 ms 43464 KB Output is correct
15 Correct 542 ms 41132 KB Output is correct
16 Correct 531 ms 39896 KB Output is correct
17 Correct 509 ms 39596 KB Output is correct
18 Correct 567 ms 41548 KB Output is correct
19 Correct 520 ms 41416 KB Output is correct
20 Correct 534 ms 42148 KB Output is correct
21 Correct 520 ms 41352 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8408 KB Output is correct
2 Correct 17 ms 8236 KB Output is correct
3 Correct 20 ms 8276 KB Output is correct
4 Correct 16 ms 8276 KB Output is correct
5 Correct 17 ms 8336 KB Output is correct
6 Correct 17 ms 8276 KB Output is correct
7 Incorrect 16 ms 8276 KB Output isn't correct
8 Halted 0 ms 0 KB -