oj.uz

Submission #697077

# Submission time Handle Problem Language Result Execution time Memory
697077 2023-02-08T07:35:37 Z baojiaopisu Parkovi (COCI22_parkovi) C++17
40 / 110
 1222 ms 36276 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, int 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;

	assert(t[u] >= -lim);

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

	if(!ok[u] && -(t[u] - wpar) > lim) {
		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:139:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |     if(!used[i] && ans.size() < k) ans.pb(i);
      |                    ~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:153:17: warning: unused variable 'ddd' [-Wunused-variable]
  153 |     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 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Incorrect 3 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 412 ms 33320 KB Output is correct
2 Correct 405 ms 34036 KB Output is correct
3 Correct 309 ms 14748 KB Output is correct
4 Correct 1110 ms 13924 KB Output is correct
5 Correct 1054 ms 13680 KB Output is correct
6 Correct 1086 ms 13576 KB Output is correct
7 Correct 1119 ms 13652 KB Output is correct
8 Correct 1222 ms 14112 KB Output is correct
9 Correct 1121 ms 13900 KB Output is correct
10 Correct 1183 ms 14084 KB Output is correct
11 Correct 726 ms 15540 KB Output is correct
12 Correct 723 ms 15892 KB Output is correct
13 Correct 814 ms 16904 KB Output is correct
14 Correct 731 ms 15716 KB Output is correct
15 Correct 698 ms 15148 KB Output is correct
16 Correct 722 ms 15936 KB Output is correct
17 Correct 688 ms 15044 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 34508 KB Output is correct
2 Correct 419 ms 33732 KB Output is correct
3 Correct 390 ms 32272 KB Output is correct
4 Correct 389 ms 32208 KB Output is correct
5 Correct 444 ms 35232 KB Output is correct
6 Correct 458 ms 34628 KB Output is correct
7 Correct 480 ms 35660 KB Output is correct
8 Correct 428 ms 34636 KB Output is correct
9 Correct 440 ms 34480 KB Output is correct
10 Correct 417 ms 33996 KB Output is correct
11 Correct 398 ms 32844 KB Output is correct
12 Correct 506 ms 36276 KB Output is correct
13 Correct 525 ms 36256 KB Output is correct
14 Correct 466 ms 35348 KB Output is correct
15 Correct 406 ms 33864 KB Output is correct
16 Correct 386 ms 32672 KB Output is correct
17 Correct 409 ms 32564 KB Output is correct
18 Correct 403 ms 34008 KB Output is correct
19 Correct 413 ms 34480 KB Output is correct
20 Correct 419 ms 34996 KB Output is correct
21 Correct 434 ms 34120 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 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -