Submission #880620

#TimeUsernameProblemLanguageResultExecution timeMemory
880620tsumondaiParkovi (COCI22_parkovi)C++14
0 / 110
395 ms37212 KiB
#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 != 0) 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(0,0)>0 || flag[0]==0) marked[0]=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; u--, v--; 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(0,0)>0 || flag[0]==0) marked[0]=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:96: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]
   96 |  foru(i,1,n) if (res.size()<k && marked[i]==0) res.pb(i);
      |                  ~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...