Submission #880628

#	Time	Username	Problem	Language	Result	Execution time	Memory
880628		tsumondai	Parkovi (COCI22_parkovi)	C++14	110 / 110	764 ms	35280 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2e5 + 5;
 
const int oo = 1e18, mod = 1e9 + 7;
 
int n, m, k, mid, uk, flag[N], marked[N];
vector<ii> adj[N];
vector<int> res;
 
 
int dfs(int x, int par) {
    if (adj[x].size() == 1 && x != 1) return 0;
    int mi = (1ll << 60), ma = -(1ll << 60);
    for (auto tr : adj[x]) {
        int y = tr.fi;
        int d = tr.se;
        if (y == par) continue;
        int a = dfs(y, x);
        if (a == 0 && flag[y] == 1) {
            mi = min(mi, 0ll);
            ma = max(ma, 0ll);
            continue;
        }
        if (a < 0 && a + d <= 0) flag[x] = 1;
 
        if (a < 0 && a + d > 0) a = 0;
        else a += d;
 
        if (a > mid) {
            uk++;
            marked[y] = 1;
            a = min(-mid + d, 0ll);
            if (-mid + d <= 0) flag[x] = 1;
            flag[y] = 1;
        }
 
 
        ma = max(ma, a);
        mi = min(mi, a);
    }
    if (-mi >= ma) {
        return mi;
    }
    return ma;
}
 
 
int binary_search(int lo, int hi) {
    while (lo < hi) {
        mid = lo + (hi-lo)/2;
        uk=0;
        memset(flag, 0, sizeof(flag));
        memset(marked, 0, sizeof(marked));
        if (dfs(1,0)>0 || flag[1]==0) marked[1]=1, uk++;
 
        if (uk<=k)
            hi = mid;
        else
            lo = mid+1;
    }
   	return lo; 
}
 
 
void process() {
	res.clear();
	cin >> n >> k;
	foru(i,1,n-1) {
		int u, v, w; cin >> u >> v >> w;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}
	mid=binary_search(0, oo);
	uk=0;
	cout << mid << '\n';
	memset(flag, 0, sizeof(flag));
	memset(marked, 0, sizeof(marked));
	if (dfs(1,0)>0 || flag[1]==0) marked[1]=1, uk++;
	foru(i,1,n) if (marked[i]==1) res.pb(i);
	foru(i,1,n) if (res.size()<k && marked[i]==0) res.pb(i);
	for (auto x: res) cout << x << ' ';
 
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}
 
/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI 
Flow:
 
*/

Compilation message (stderr)

Main.cpp: In function 'void process()':
Main.cpp:95:28: 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 |  foru(i,1,n) if (res.size()<k && marked[i]==0) res.pb(i);
      |                  ~~~~~~~~~~^~

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