Submission #1266320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266320		namhh	Parkovi (COCI22_parkovi)	C++20	110 / 110	490 ms	36784 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
int n,k,rem[N],emilia[N],cv[N],mid;
vector<pii>adj[N];
vector<int>res;
void dfs(int u, int p){
	for(auto[v,w]: adj[u]){
		if(v != p){
			dfs(v,u);
			if(emilia[v] != -1){
				if(emilia[v] >= w) emilia[u] = max(emilia[u],emilia[v]-w);
				continue;
			}
			if(rem[v]+w > mid){
				cv[v] = 1;
				rem[v] = 0;
				emilia[v] = mid;
				if(mid >= w) emilia[u] = max(emilia[u],mid-w);
			}
			else rem[u] = max(rem[u],rem[v]+w);
		}
	}
	if(emilia[u] >= rem[u]) rem[u] = 0;
	else emilia[u] = -1;
	if(u == 1 && emilia[u] == -1) cv[u] = 1;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	int tot = 0;
	for(int i = 1; i < n; i++){
		int u,v,c;
		cin >> u >> v >> c;
		adj[u].push_back({v,c});
		adj[v].push_back({u,c});
		tot += c;
	}
	int l = 0;
	int r = tot;
	int ans;
	while(l <= r){
		memset(cv,0,sizeof(cv));
		memset(emilia,-1,sizeof(emilia));
		memset(rem,0,sizeof(rem));
	    mid = (l+r)/2;
	    dfs(1,0);
	    int cnt = 0;
	    for(int i = 1; i <= n; i++) cnt += cv[i];
	    if(cnt <= k){
	    	ans = mid;
	    	r = mid-1;
	    	res.clear();
	    	for(int i = 1; i <= n; i++) if(cv[i]) res.push_back(i);
		}
		else l = mid+1;
	}
	cout << ans << "\n";
	memset(cv,0,sizeof(cv));
	for(auto it: res){
        cout << it << " ";
        cv[it] = 1;
    }
	k -= res.size();
	for(int i = 1; i <= n; i++){
		if(k == 0) break;
		if(cv[i] == 0){
			cout << i << " ";
			k--;
		}
	}
}
//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--

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