Submission #725856

#	Time	Username	Problem	Language	Result	Execution time	Memory
725856		pavement	Pastiri (COI20_pastiri)	C++17	23 / 100	1093 ms	280832 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 init(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;
		init(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)];
}

int tot_sz, sz[500005], par[500005], lvl[500005], dist_cent[25][500005];

int get_sz(int n, int e = -1) {
	sz[n] = 1;
	for (auto u : adj[n]) if (u != e && lvl[u] == -1) {
		sz[n] += get_sz(u, n);
	}
	return sz[n];
}

int cent(int n, int e = -1) {
	for (auto u : adj[n]) if (u != e && lvl[u] == -1)
		if (tot_sz / 2 < sz[u]) return cent(u, n);
	return n;
}

void decomp(int n, int e = -1) {
	// find centroid of component containing node n
	get_sz(n);
	tot_sz = sz[n];
	int c = cent(n);
	par[c] = e;
	if (e != -1) lvl[c] = lvl[e] + 1;
	else lvl[c] = 0;
	for (auto u : adj[c]) {
		if (lvl[u] == -1) decomp(u, c);
	}
}

set<int> S[500005];

void upd(int u) {
	for (int cur = u, k = 0; cur != -1; cur = par[cur], k++) {
		S[cur].insert(cl[u] - dist_cent[k][u]);
	}
}

bool qry(int u) {
	for (int cur = u, k = 0; cur != -1; cur = par[cur], k++) {
		if (S[cur].find(dist_cent[k][u]) != S[cur].end()) return 1;
	}
	return 0;
}

main() {
	memset(anc, -1, sizeof anc);
	memset(lvl, -1, sizeof lvl);
	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);
	}
	init(1);
	decomp(1);
	for (int i = 1; i <= N; i++)
		for (int cur = i, k = 0; cur != -1; cur = par[cur], k++) {
			dist_cent[k][i] = dist(i, cur);
		}
	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];
		if (qry(u)) {
			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);
		upd(u);
	}
	cout << placed.size() << '\n';
	for (auto u : placed) cout << u << ' ';
	cout << '\n';
}

Compilation message (stderr)

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

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