Submission #880622

#	Time	Username	Problem	Language	Result	Execution time	Memory
880622		tsumondai	Parkovi (COCI22_parkovi)	C++14	110 / 110	1030 ms	39036 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 != 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 << ' ';*/

	int lo = 0, hi = (1LL << 60);
    while (lo < hi) {
        mid = (lo + hi) / 2;
        uk = 0;
        memset(flag, 0, sizeof flag);
        memset(marked, 0, sizeof marked);
        if (dfs(0, 0) > 0) marked[0] = 1, uk++;
        else if (flag[0] == 0) marked[0] = 1, uk++;

        //cout << endl << uk << endl;
        //cout << mid << " " << uk << endl;

        if (uk <= k) hi = mid;
        else         lo = mid + 1;
    }

    mid = lo;
    uk = 0;
    memset(flag, 0, sizeof flag);
    memset(marked, 0, sizeof marked);
    if (dfs(0, 0) > 0) marked[0] = 1, uk++;
    else if (flag[0] == 0) marked[0] = 1, uk++;

    cout << lo << "\n";
    vector <int> out;
    foru(i,0,n-1) if (marked[i] == 1) out.push_back(i + 1);
    foru(i,0,n-1) if (out.size() < k && marked[i] == 0) out.push_back(i + 1);
    for (int x : out) cout << x << " "; cout << "\n";

}

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:125:34: 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]
  125 |     foru(i,0,n-1) if (out.size() < k && marked[i] == 0) out.push_back(i + 1);
      |                       ~~~~~~~~~~~^~~
Main.cpp:126:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  126 |     for (int x : out) cout << x << " "; cout << "\n";
      |     ^~~
Main.cpp:126:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  126 |     for (int x : out) cout << x << " "; cout << "\n";
      |                                         ^~~~

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