Submission #879747

#	Time	Username	Problem	Language	Result	Execution time	Memory
879747		Alora	Parkovi (COCI22_parkovi)	C++17	0 / 110	331 ms	38624 KiB

Main

#include <bits/stdc++.h>
#define Alora "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define all(v) v.begin(), v.end()
#define pb push_back
#define maxn 200005
const int M = 1e9 + 7;
using namespace std;
int n, k, place[maxn], ans;
ll reach[maxn], dist[maxn], sum, oo = 1e18;
vector <pii> g[maxn];
void dfs(int u, int fa, int lim){
    for(auto [v, w]: g[u]) if(v != fa){
        dfs(v, u, lim);
        if(reach[v] + min(1ll*w, dist[v]) <= lim){
            if(reach[v] + dist[v] > lim)
                reach[u] = max(reach[u], reach[v] + w);
            dist[u] = min(dist[u], dist[v] + w);
        }
        else{
            place[v] = 1; ans++;
            dist[u] = min(dist[u], 1ll*w);
        }
    }
}
int cnt(ll lim){
    fi(i, 1, n) reach[i] = 0, dist[i] = oo, place[i] = 0;
    ans = 0;
    dfs(1, 1, lim);
    if(reach[1] + dist[1] > lim) ans++, place[1] = 1;
    return ans;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	if(fopen(Alora".inp", "r")){
    freopen(Alora".inp", "r", stdin);
    freopen(Alora".out", "w", stdout);}
    cin >> n >> k;
    fi(i, 1, n - 1){
        int u, v, w; cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
        sum += w;
    }
    ll d = 0, c = sum;
    while(d <= c){
        ll g = (d + c)/2;
        if(cnt(g) <= k) c = g - 1;
        else d = g + 1;
    }
    cout << d << '\n';
    int x = cnt(d);
    fi(i, 1, n){
        if(place[i]) cout << i << " ";
        else if(x < k) x++, cout << i << " ";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen(Alora".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen(Alora".out", "w", stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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