oj.uz

Submission #1003962

# Submission time Handle Problem Language Result Execution time Memory
1003962 2024-06-20T20:57:01 Z vjudge1 Pastiri (COI20_pastiri) C++17
0 / 100
 1000 ms 60368 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;

	vector<vector<int>> graph(n);
	for (int i = 0; i < n-1; ++i) {
		int u, v;
		cin >> u >> v;

		--u; --v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	vector<bool> ovelha(n);
	for (int i = 0; i < k; ++i) {
		int u;
		cin >> u;

		ovelha[u - 1] = true;
	}

	vector<vector<int>> cover(n);

	function<pair<int, vector<int>> (int, int)> dfs = [&](int u, int p) {
		if (ovelha[u]) return make_pair(0, vector<int>{u});

		pair<int, vector<int>> best = make_pair((int)1e9, vector<int>());
		for (int v: graph[u]) if (v != p) {
			auto [d, xs] = dfs(v, u);
			if (d + 1 < best.first ) {
				// cover[v] = best.second;
				best = make_pair(d + 1, move(xs));
			}
			else if (d + 1 == best.first) {
				if (best.second.size() > xs.size())
					for (int x: xs)
						best.second.push_back(x);
				else {
					for (int x: best.second)
						xs.push_back(x);
					best.second = move(xs);
				}
			}
			// else cover[v] = xs;
		}

		// cerr << "DFS " << u << " " << best.first << "\n";

		return best;
	};

	for (int i = 0; i < n; ++i)
		cover[i] = dfs(i, i).second;

	// for (int i = 0; i < n; ++i) {
	// 	cerr << i << " -> ";
	// 	for (int x: cover[i])
	// 		cerr << x << " ";
	// 	cerr << "\n";
	// }

	vector<pair<int, int>> sz(n);
	for (int i = 0; i < n; ++i)
		sz[i] = make_pair(cover[i].size(), i);

	sort(sz.rbegin(), sz.rend());

	vector<int> ans;

	vector<bool> taken(n);
	for (auto [_, idx]: sz) {
		// cerr << "-> " << idx << "\n";
		bool ok = false;
		for (int x: cover[idx])
			if (!taken[x]) ok = true;

		if (ok) {
			ans.push_back(idx);
			for (int x: cover[idx])
				taken[x] = true;
		}
	}

	cout << ans.size() << "\n";

	for (int x: ans)
		cout << x+1 << " ";
	cout << "\n";
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 333 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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