oj.uz

Submission #697078

# Submission time Handle Problem Language Result Execution time Memory
697078 2023-02-08T07:41:01 Z baojiaopisu Parkovi (COCI22_parkovi) C++17
40 / 110
 1167 ms 36320 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e9;
const int N = 2e5 + 10;

vector<pii> g[N];
ll t[N];
bool used[N], ok[N];
int cnt = 0;

void dfs(int u, int par, ll wpar, ll lim) {
	ll r = 0, c = 0;
	t[u] = ok[u] = 0;
	for(auto [v, w] : g[u]) {
		if(v != par) {
			dfs(v, u, w, lim);
			if(t[v] - w >= 0) ok[u] = true;
			if(ok[v]) maximize(r, t[v] - w);
			else maximize(c, (-t[v]) + w);
		}
	}

	if(r >= c) t[u] = r;
	else t[u] = -c;

	if(u == 1 && !ok[u]) {
		used[u] = 1;
		++cnt;
		return;
	}

	if(!ok[u] && -(t[u] - wpar) > lim) {
		assert(t[u] <= 0);
		t[u] = lim;
		ok[u] = true;
		used[u] = true;
		++cnt;
	}
}

void BaoJiaoPisu() {
	int n, k; cin >> n >> k;
	for(int i = 1; i < n; i++) {
		int u, v, w; cin >> u >> v >> w;
		g[u].pb(mp(v, w));
		g[v].pb(mp(u, w));
	}

	if(k == n) {
		cout << 0 << '\n';
		for(int i = 1; i <= n; i++) cout << i << " ";
		return;
	}

	vector<int> ans;
	ll l = 1, r = INF * n, res = -1;
	while(l <= r) {
		ll mid = (l + r) >> 1;
		for(int i = 1; i <= n; i++) used[i] = false;
			
		cnt = 0;
		dfs(1, 0, 0, mid);
		
		if(cnt <= k) {
			ans.clear();
			res = mid;
			for(int i = 1; i <= n; i++) {
				if(used[i]) ans.pb(i);
			}

			for(int i = 1; i <= n; i++) {
				if(!used[i] && ans.size() < k) ans.pb(i);
			}
			r = mid - 1;
		} else l = mid + 1;
	}

	cout << res << '\n';
	for(auto x : ans) cout << x << " ";
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        BaoJiaoPisu();
    }
}

Compilation message

Main.cpp: In function 'void BaoJiaoPisu()':
Main.cpp:138:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  138 |     if(!used[i] && ans.size() < k) ans.pb(i);
      |                    ~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:152:17: warning: unused variable 'ddd' [-Wunused-variable]
  152 |     int tc = 1, ddd = 0;
      |                 ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Incorrect 2 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 33276 KB Output is correct
2 Correct 408 ms 33916 KB Output is correct
3 Correct 373 ms 14648 KB Output is correct
4 Correct 1114 ms 13860 KB Output is correct
5 Correct 977 ms 13568 KB Output is correct
6 Correct 1086 ms 13576 KB Output is correct
7 Correct 1167 ms 13716 KB Output is correct
8 Correct 1112 ms 14060 KB Output is correct
9 Correct 1090 ms 13896 KB Output is correct
10 Correct 1129 ms 14092 KB Output is correct
11 Correct 799 ms 15628 KB Output is correct
12 Correct 744 ms 15776 KB Output is correct
13 Correct 755 ms 16904 KB Output is correct
14 Correct 697 ms 15712 KB Output is correct
15 Correct 738 ms 15192 KB Output is correct
16 Correct 703 ms 15884 KB Output is correct
17 Correct 729 ms 15116 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 34468 KB Output is correct
2 Correct 408 ms 33736 KB Output is correct
3 Correct 375 ms 32384 KB Output is correct
4 Correct 378 ms 32204 KB Output is correct
5 Correct 453 ms 35236 KB Output is correct
6 Correct 503 ms 34556 KB Output is correct
7 Correct 496 ms 35644 KB Output is correct
8 Correct 410 ms 34732 KB Output is correct
9 Correct 415 ms 34480 KB Output is correct
10 Correct 416 ms 33892 KB Output is correct
11 Correct 404 ms 32928 KB Output is correct
12 Correct 531 ms 36280 KB Output is correct
13 Correct 533 ms 36320 KB Output is correct
14 Correct 459 ms 35344 KB Output is correct
15 Correct 393 ms 33864 KB Output is correct
16 Correct 391 ms 32684 KB Output is correct
17 Correct 381 ms 32564 KB Output is correct
18 Correct 413 ms 34204 KB Output is correct
19 Correct 407 ms 34480 KB Output is correct
20 Correct 438 ms 35140 KB Output is correct
21 Correct 448 ms 34160 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Incorrect 2 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -