oj.uz

Submission #697075

# Submission time Handle Problem Language Result Execution time Memory
697075 2023-02-08T07:20:40 Z baojiaopisu Parkovi (COCI22_parkovi) C++17
40 / 110
 1180 ms 38128 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;

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4948 KB Output is correct
6 Correct 3 ms 5044 KB Output is correct
7 Incorrect 3 ms 5036 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 423 ms 33272 KB Output is correct
2 Correct 434 ms 35872 KB Output is correct
3 Correct 362 ms 16404 KB Output is correct
4 Correct 1080 ms 15648 KB Output is correct
5 Correct 1058 ms 15376 KB Output is correct
6 Correct 1065 ms 15372 KB Output is correct
7 Correct 1174 ms 15376 KB Output is correct
8 Correct 1180 ms 15900 KB Output is correct
9 Correct 1084 ms 15600 KB Output is correct
10 Correct 1179 ms 15880 KB Output is correct
11 Correct 750 ms 17308 KB Output is correct
12 Correct 683 ms 17668 KB Output is correct
13 Correct 785 ms 18696 KB Output is correct
14 Correct 741 ms 17440 KB Output is correct
15 Correct 742 ms 16904 KB Output is correct
16 Correct 741 ms 17708 KB Output is correct
17 Correct 728 ms 16892 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 34548 KB Output is correct
2 Correct 416 ms 35524 KB Output is correct
3 Correct 390 ms 34124 KB Output is correct
4 Correct 372 ms 33996 KB Output is correct
5 Correct 426 ms 36968 KB Output is correct
6 Correct 456 ms 36348 KB Output is correct
7 Correct 476 ms 37588 KB Output is correct
8 Correct 441 ms 36528 KB Output is correct
9 Correct 426 ms 36240 KB Output is correct
10 Correct 432 ms 35676 KB Output is correct
11 Correct 405 ms 34608 KB Output is correct
12 Correct 503 ms 38068 KB Output is correct
13 Correct 545 ms 38128 KB Output is correct
14 Correct 484 ms 37136 KB Output is correct
15 Correct 414 ms 35640 KB Output is correct
16 Correct 408 ms 34556 KB Output is correct
17 Correct 404 ms 34252 KB Output is correct
18 Correct 408 ms 35868 KB Output is correct
19 Correct 428 ms 36132 KB Output is correct
20 Correct 438 ms 36572 KB Output is correct
21 Correct 427 ms 35896 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4948 KB Output is correct
6 Correct 3 ms 5044 KB Output is correct
7 Incorrect 3 ms 5036 KB Output isn't correct
8 Halted 0 ms 0 KB -