oj.uz

Submission #725856

# Submission time Handle Problem Language Result Execution time Memory
725856 2023-04-18T07:42:29 Z pavement Pastiri (COI20_pastiri) C++17
23 / 100
 1000 ms 280832 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 <= 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

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 1068 ms 280832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 138248 KB Output is correct
2 Correct 80 ms 138224 KB Output is correct
3 Execution timed out 1093 ms 200176 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 137676 KB Output is correct
2 Correct 62 ms 137636 KB Output is correct
3 Correct 60 ms 137764 KB Output is correct
4 Correct 59 ms 137548 KB Output is correct
5 Correct 62 ms 137760 KB Output is correct
6 Correct 61 ms 137772 KB Output is correct
7 Correct 60 ms 137676 KB Output is correct
8 Correct 60 ms 137672 KB Output is correct
9 Correct 59 ms 137592 KB Output is correct
10 Correct 60 ms 137572 KB Output is correct
11 Correct 60 ms 137424 KB Output is correct
12 Correct 60 ms 137432 KB Output is correct
13 Correct 60 ms 137700 KB Output is correct
14 Correct 61 ms 137824 KB Output is correct
15 Correct 61 ms 137752 KB Output is correct

Subtask #4
0 / 51.0

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