oj.uz

Submission #696661

# Submission time Handle Problem Language Result Execution time Memory
696661 2023-02-07T03:06:55 Z SanguineChameleon Parkovi (COCI22_parkovi) C++17
20 / 110
 3000 ms 24332 KB 
// BEGIN BOILERPLATE CODE

#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool kami_loc = true;
	const long long kami_seed = 69420;
#else
	const bool kami_loc = false;
	const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif

const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);

long long rand_range(long long rmin, long long rmax) {
	uniform_int_distribution<long long> rdist(rmin, rmax);
	return rdist(kami_gen);
}

long double rand_real(long double rmin, long double rmax) {
	uniform_real_distribution<long double> rdist(rmin, rmax);
	return rdist(kami_gen);
}

void file_io(string fi, string fo) {
	if (fi != "" && (!kami_loc || fi == kami_fi)) {
		freopen(fi.c_str(), "r", stdin);
	}
	if (fo != "" && (!kami_loc || fo == kami_fo)) {
		freopen(fo.c_str(), "w", stdout);
	}
}

void set_up() {
	if (kami_loc) {
		file_io(kami_fi, kami_fo);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

void just_do_it();

void just_exec_it() {
	if (kami_loc) {
		auto pstart = chrono::steady_clock::now();
		just_do_it();
		auto pend = chrono::steady_clock::now();
		long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
		string bar(50, '=');
		cout << '\n' << bar << '\n';
		cout << "Time: " << ptime << " ms" << '\n';
	}
	else {
		just_do_it();
	}
}

int main() {
	set_up();
	just_exec_it();
	return 0;
}

// END BOILERPLATE CODE

// BEGIN MAIN CODE

const long long inf = 1e18L + 20;
const int ms = 2e5 + 20;
vector<pair<int, int>> adj[ms];
bool f[ms];
long long de[ms];
long long mx[ms];
int best = -1;
long long res = inf;
int n, k;

void dfs(int u, int pr) {
	for (auto x: adj[u]) {
		int v = x.first;
		int w = x.second;
		if (v != pr) {
			de[v] = de[u] + w;
			dfs(v, u);
		}
	}
}

void sub2() {
	de[1] = 0;
	dfs(1, -1);
	int d1 = 1;
	for (int i = 1; i <= n; i++) {
		if (de[i] > de[d1]) {
			d1 = i;
		}
	}
	de[d1] = 0;
	dfs(d1, -1);
	int d2 = 1;
	for (int i = 1; i <= n; i++) {
		mx[i] = max(mx[i], de[i]);
		if (de[i] > de[d2]) {
			d2 = i;
		}
	}
	de[d2] = 0;
	dfs(d2, -1);
	for (int i = 1; i <= n; i++) {
		mx[i] = max(mx[i], de[i]);
	}
	int best = 1;
	for (int i = 1; i <= n; i++) {
		if (mx[i] < mx[best]) {
			best = i;
		}
	}
	cout << mx[best] << '\n';
	cout << best << '\n';
}

void just_do_it() {
	cin >> n >> k;
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	if (k == 1) {
		sub2();
		return;
	}
	for (int i = 0; i < (1 << n); i++) {
		if (__builtin_popcount(i) != k) {
			continue;
		}
		for (int j = 0; j < n; j++) {
			if ((i >> j) & 1) {
				f[j + 1] = true;
			}
			else {
				f[j + 1] = false;
			}
		}
		long long cur = 0;
		for (int j = 1; j <= n; j++) {
			de[j] = 0;
			dfs(j, -1);
			long long mi = inf;
			for (int k = 1; k <= n; k++) {
				if (f[k]) {
					mi = min(mi, de[k]);
				}
			}
			cur = max(cur, mi);
		}
		if (cur < res) {
			res = cur;
			best = i;
		}
	}
	cout << res << '\n';
	for (int i = 0; i < n; i++) {
		if ((best >> i) & 1) {
			cout << (i + 1) << " ";
		}
	}
}

// END MAIN CODE

Compilation message

Main.cpp: In function 'void file_io(std::string, std::string)':
Main.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Correct 8 ms 5028 KB Output is correct
3 Correct 11 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 6 ms 5028 KB Output is correct
6 Correct 63 ms 4948 KB Output is correct
7 Correct 72 ms 4948 KB Output is correct
8 Correct 27 ms 4948 KB Output is correct
9 Correct 339 ms 5016 KB Output is correct
10 Correct 29 ms 4948 KB Output is correct
11 Correct 181 ms 5028 KB Output is correct
12 Correct 341 ms 4948 KB Output is correct
13 Correct 11 ms 4948 KB Output is correct
14 Correct 185 ms 5032 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 22428 KB Output is correct
2 Correct 85 ms 24332 KB Output is correct
3 Correct 91 ms 20380 KB Output is correct
4 Correct 144 ms 19072 KB Output is correct
5 Correct 153 ms 18584 KB Output is correct
6 Correct 133 ms 18664 KB Output is correct
7 Correct 145 ms 17488 KB Output is correct
8 Correct 142 ms 18056 KB Output is correct
9 Correct 177 ms 18468 KB Output is correct
10 Correct 138 ms 18804 KB Output is correct
11 Correct 129 ms 20012 KB Output is correct
12 Correct 113 ms 19344 KB Output is correct
13 Correct 121 ms 20560 KB Output is correct
14 Correct 109 ms 18004 KB Output is correct
15 Correct 103 ms 18000 KB Output is correct
16 Correct 115 ms 19196 KB Output is correct
17 Correct 99 ms 18728 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 23332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Correct 8 ms 5028 KB Output is correct
3 Correct 11 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 6 ms 5028 KB Output is correct
6 Correct 63 ms 4948 KB Output is correct
7 Correct 72 ms 4948 KB Output is correct
8 Correct 27 ms 4948 KB Output is correct
9 Correct 339 ms 5016 KB Output is correct
10 Correct 29 ms 4948 KB Output is correct
11 Correct 181 ms 5028 KB Output is correct
12 Correct 341 ms 4948 KB Output is correct
13 Correct 11 ms 4948 KB Output is correct
14 Correct 185 ms 5032 KB Output is correct
15 Correct 65 ms 22428 KB Output is correct
16 Correct 85 ms 24332 KB Output is correct
17 Correct 91 ms 20380 KB Output is correct
18 Correct 144 ms 19072 KB Output is correct
19 Correct 153 ms 18584 KB Output is correct
20 Correct 133 ms 18664 KB Output is correct
21 Correct 145 ms 17488 KB Output is correct
22 Correct 142 ms 18056 KB Output is correct
23 Correct 177 ms 18468 KB Output is correct
24 Correct 138 ms 18804 KB Output is correct
25 Correct 129 ms 20012 KB Output is correct
26 Correct 113 ms 19344 KB Output is correct
27 Correct 121 ms 20560 KB Output is correct
28 Correct 109 ms 18004 KB Output is correct
29 Correct 103 ms 18000 KB Output is correct
30 Correct 115 ms 19196 KB Output is correct
31 Correct 99 ms 18728 KB Output is correct
32 Execution timed out 3068 ms 23332 KB Time limit exceeded
33 Halted 0 ms 0 KB -