Submission #725770

#	Time	Username	Problem	Language	Result	Execution time	Memory
725770		pavement	Pastiri (COI20_pastiri)	C++17	41 / 100	1087 ms	175044 KiB

pastiri

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, K, dep[500005], cl[500005], anc[25][500005];
ii o[500005];
vector<int> placed, adj[500005];
queue<ii> Q;

void dfs(int n, int e = -1) {
	anc[0][n] = e;
	for (int k = 1; k <= 20; k++) {
		if (anc[k - 1][n] == -1) break;
		anc[k][n] = anc[k - 1][anc[k - 1][n]];
	}
	for (auto u : adj[n]) if (u != e) {
		dep[u] = dep[n] + 1;
		dfs(u, n);
	}
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	for (int k = 20; k >= 0; k--)
		if (dep[v] - (1 << k) >= dep[u]) {
			v = anc[k][v];
		}
	if (u == v) return u;
	for (int k = 20; k >= 0; k--)
		if (anc[k][u] != anc[k][v]) {
			u = anc[k][u];
			v = anc[k][v];
		}
	return anc[0][u];
}

int dist(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

main() {
	memset(anc, -1, sizeof anc);
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	cin >> N >> K;
	for (int i = 1, u, v; i < N; i++) {
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1);
	for (int i = 1; i <= N; i++) {
		cl[i] = (int)1e9;
	}
	for (int i = 1; i <= K; i++) {
		cin >> o[i].second;
		o[i].first = dep[o[i].second];
		Q.emplace(0, o[i].second);
		cl[o[i].second] = 0;
	}
	while (!Q.empty()) {
		auto [d, u] = Q.front();
		Q.pop();
		if (d != cl[u]) continue;
		for (auto v : adj[u]) {
			if (cl[v] > d + 1) {
				cl[v] = d + 1;
				Q.emplace(cl[v], v);
			}
		}
	}
	sort(o + 1, o + 1 + K, greater<ii>());
	for (int i = 1; i <= K; i++) {
		auto [d, u] = o[i];
		bool done = 0;
		for (auto v : placed) {
			if (dist(u, v) == cl[v]) {
				done = 1;
				break;
			}
		}
		if (done) {
			continue;
		}
		for (int k = 20; k >= 0; k--) {
			if (anc[k][u] != -1 && cl[anc[k][u]] == d - dep[anc[k][u]]) {
				u = anc[k][u];
			}
		}
		placed.pb(u);
	}
	cout << placed.size() << '\n';
	for (auto u : placed) cout << u << ' ';
	cout << '\n';
}

Compilation message (stderr)

pastiri.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main() {
      | ^~~~

• Subtask 1: 0 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51