oj.uz

Submission #725770

# Submission time Handle Problem Language Result Execution time Memory
725770 2023-04-18T03:24:53 Z pavement Pastiri (COI20_pastiri) C++17
41 / 100
 1000 ms 175044 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 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

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 163396 KB Output is correct
2 Correct 490 ms 163512 KB Output is correct
3 Correct 486 ms 163552 KB Output is correct
4 Execution timed out 1087 ms 175044 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 110140 KB Output is correct
2 Correct 57 ms 110144 KB Output is correct
3 Correct 678 ms 144716 KB Output is correct
4 Correct 681 ms 149580 KB Output is correct
5 Correct 826 ms 140004 KB Output is correct
6 Correct 910 ms 142292 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 110028 KB Output is correct
2 Correct 45 ms 109968 KB Output is correct
3 Correct 75 ms 110060 KB Output is correct
4 Correct 71 ms 110028 KB Output is correct
5 Correct 59 ms 110164 KB Output is correct
6 Correct 61 ms 110056 KB Output is correct
7 Correct 46 ms 109928 KB Output is correct
8 Correct 47 ms 109948 KB Output is correct
9 Correct 47 ms 110036 KB Output is correct
10 Correct 46 ms 110020 KB Output is correct
11 Correct 44 ms 109900 KB Output is correct
12 Correct 46 ms 109964 KB Output is correct
13 Correct 62 ms 109936 KB Output is correct
14 Correct 52 ms 110000 KB Output is correct
15 Correct 57 ms 110044 KB Output is correct

Subtask #4
0 / 51.0

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