oj.uz

Submission #725858

# Submission time Handle Problem Language Result Execution time Memory
725858 2023-04-18T07:45:18 Z pavement Pastiri (COI20_pastiri) C++17
23 / 100
 1000 ms 278216 KB 
#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 <= 18; 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 = 18; k >= 0; k--)
		if (dep[v] - (1 << k) >= dep[u]) {
			v = anc[k][v];
		}
	if (u == v) return u;
	for (int k = 18; 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);
	}
}

unordered_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 = 18; 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

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

Subtask #1
0 / 8.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 142156 KB Output is correct
2 Correct 68 ms 142292 KB Output is correct
3 Execution timed out 1083 ms 203512 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 141624 KB Output is correct
2 Correct 59 ms 141640 KB Output is correct
3 Correct 63 ms 141716 KB Output is correct
4 Correct 62 ms 141584 KB Output is correct
5 Correct 63 ms 141652 KB Output is correct
6 Correct 63 ms 141704 KB Output is correct
7 Correct 62 ms 141648 KB Output is correct
8 Correct 62 ms 141608 KB Output is correct
9 Correct 61 ms 141488 KB Output is correct
10 Correct 60 ms 141492 KB Output is correct
11 Correct 60 ms 141436 KB Output is correct
12 Correct 60 ms 141376 KB Output is correct
13 Correct 61 ms 141516 KB Output is correct
14 Correct 63 ms 141768 KB Output is correct
15 Correct 61 ms 141764 KB Output is correct

Subtask #4
0 / 51.0

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