oj.uz

Submission #1103641

# Submission time Handle Problem Language Result Execution time Memory
1103641 2024-10-21T12:37:09 Z SalihSahin Parkovi (COCI22_parkovi) C++14
10 / 110
 801 ms 56600 KB 
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int mod = 998244353;
const int inf = 1e17;
const int N = 2e5+5;
const int W = 1e9;

vector<pair<int, int> > adj[N];
vector<int> distopar(N);
vector<int> taken, vis(N);

array<int, 3> dfs(int node, int par, int limit, bool tk){ // max distance, park count
    vector<array<int, 3> > ch;
    for(auto itr: adj[node]){
        if(itr.first != par){
            distopar[itr.first] = itr.second;
            array<int, 3> arr = dfs(itr.first, node, limit, tk);
            ch.pb(arr);
        }
    }
    array<int, 3> calc = {0, 0, 0};
    int mn = inf;
    for(auto itr: ch){
        if(itr[2] == 0) mn = min(mn, itr[0]);
    }

    for(auto itr: ch){
        calc[1] += itr[1];
        if(itr[2] == 1 && mn + itr[0] <= limit) continue;

        if(itr[2] == calc[2]) calc[0] = max(calc[0], itr[0]);
        else if(itr[2] > calc[2]){
            calc[0] = itr[0];
            calc[2] = itr[2];
        }
    }

    if(!ch.size()){
        calc = {0, 0, 1};
    }

    if(calc[2] == 0){ // phase 2
        if(calc[0] + distopar[node] > limit){
            calc[0] = 0;
            calc[2] = 1;
        }
        else calc[0] += distopar[node];
    }
    else{
        if(calc[0] + distopar[node] > limit){
            calc[0] = 0;
            calc[1]++;
            calc[2] = 0;
            if(tk){
                taken.pb(node);
                vis[node] = 1;
            }
        }
        calc[0] += distopar[node];
    }
    return calc;
}

int32_t main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int n, k;
    cin>>n>>k;
    for(int i = 0; i < n-1; i++){
        int u, v, c;
        cin>>u>>v>>c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }


    int l = 0, r = N*W;
    while(l < r){
        int m = (l + r)/2;

        array<int, 3> check = dfs(1, 1, m, 0);


        //cout<<m<<" icin > "<<check[0]<<" "<<check[1]<<" "<<check[2]<<endl;
        if(check[1] + check[2] <= k) r = m;
        else l = m + 1;
    }

    cout<<l<<endl;
    dfs(1, 1, l, 1);
    for(int i = 1; i <= n; i++){
        if(taken.size() == k) break;
        if(vis[i]) continue;
        taken.pb(i);
    }

    for(auto itr: taken){
        cout<<itr<<" ";
    }
    cout<<endl;
    return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:95:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   95 |         if(taken.size() == k) break;
      |            ~~~~~~~~~~~~~^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8440 KB Output is correct
2 Incorrect 3 ms 8276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 49232 KB Output is correct
2 Correct 581 ms 54860 KB Output is correct
3 Correct 572 ms 35116 KB Output is correct
4 Correct 687 ms 21992 KB Output is correct
5 Correct 653 ms 21616 KB Output is correct
6 Correct 653 ms 21636 KB Output is correct
7 Correct 626 ms 20456 KB Output is correct
8 Correct 719 ms 21068 KB Output is correct
9 Correct 691 ms 21392 KB Output is correct
10 Correct 795 ms 21772 KB Output is correct
11 Correct 660 ms 25108 KB Output is correct
12 Correct 579 ms 25652 KB Output is correct
13 Correct 676 ms 27544 KB Output is correct
14 Correct 654 ms 24300 KB Output is correct
15 Correct 735 ms 23284 KB Output is correct
16 Correct 795 ms 25324 KB Output is correct
17 Correct 801 ms 23888 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 51240 KB Output is correct
2 Correct 640 ms 54284 KB Output is correct
3 Correct 575 ms 51788 KB Output is correct
4 Correct 537 ms 51788 KB Output is correct
5 Incorrect 607 ms 56600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8440 KB Output is correct
2 Incorrect 3 ms 8276 KB Output isn't correct
3 Halted 0 ms 0 KB -