Submission #1103638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103638		SalihSahin	Parkovi (COCI22_parkovi)	C++14	0 / 110	600 ms	48184 KiB

Main

#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);
            arr[0] += itr.second;
            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 if(calc[0] + distopar[node] > limit){
        calc[0] = -distopar[node];
        calc[1]++;
        calc[2] = 0;
        if(tk){
            taken.pb(node);
            vis[node] = 1;
        }
    }
    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 (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:92: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]
   92 |         if(taken.size() == k) break;
      |            ~~~~~~~~~~~~~^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60