oj.uz

Submission #714025

# Submission time Handle Problem Language Result Execution time Memory
714025 2023-03-23T14:49:21 Z vovamr Pastiri (COI20_pastiri) C++17
100 / 100
 808 ms 101964 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 5e5 + 100;
const int lg = 19;

ve<int> gr[N];
int d[N];
int up[N][lg];

inline void dfs(int v, int p) {
	up[v][0] = p;
	for (int i = 1; i < lg; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
	for (const auto &to : gr[v]) {
		if (to == p) continue;
		d[to] = d[v] + 1;
		dfs(to, v);
	}
}

inline void solve() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i < n; ++i) {
		int v, u;
		cin >> v >> u, --v, --u;
		gr[v].pb(u), gr[u].pb(v);
	}
	dfs(0, 0);
	ve<pii> a(k);
	for (auto &[x, y] : a) {
		cin >> y;
		x = d[--y];
	}
	sort(all(a));
	reverse(all(a));

	ve<int> dist(n, -1);
	queue<int> q;

	for (const auto &[x, y] : a) {
		dist[y] = 0;
		q.push(y);
	}
	while (sz(q)) {
		int v = q.front();
		q.pop();
		for (const auto &to : gr[v]) {
			if (~dist[to]) continue;
			dist[to] = dist[v] + 1;
			q.push(to);
		}
	}

	ve<int> answer, used(n);

	function<void(int)> upd = [&](int v) {
		used[v] = 1;
		for (const auto &to : gr[v]) {
			if (used[to]) continue;
			if (dist[to] != dist[v] - 1) continue;
			upd(to);
		}
	};

	for (const auto &[x, y] : a) {
		if (used[y]) continue;

		int v = y;
		for (int i = lg - 1; ~i; --i) {
			if (dist[up[v][i]] == d[y] - d[up[v][i]]) {
				v = up[v][i];
			}
		}
		answer.pb(v + 1);
		upd(v);
	}
	
	cout << sz(answer) << '\n';
	for (const auto &x : answer) cout << x << " ";
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 93912 KB Output is correct
2 Correct 236 ms 93912 KB Output is correct
3 Correct 254 ms 93844 KB Output is correct
4 Correct 323 ms 101964 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12732 KB Output is correct
2 Correct 8 ms 12628 KB Output is correct
3 Correct 520 ms 77884 KB Output is correct
4 Correct 514 ms 80332 KB Output is correct
5 Correct 688 ms 77372 KB Output is correct
6 Correct 800 ms 79496 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 7 ms 12244 KB Output is correct
3 Correct 7 ms 12244 KB Output is correct
4 Correct 10 ms 12244 KB Output is correct
5 Correct 7 ms 12308 KB Output is correct
6 Correct 9 ms 12344 KB Output is correct
7 Correct 8 ms 12244 KB Output is correct
8 Correct 8 ms 12268 KB Output is correct
9 Correct 8 ms 12244 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 7 ms 12264 KB Output is correct
12 Correct 7 ms 12200 KB Output is correct
13 Correct 7 ms 12268 KB Output is correct
14 Correct 7 ms 12372 KB Output is correct
15 Correct 8 ms 12244 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 78276 KB Output is correct
2 Correct 634 ms 78196 KB Output is correct
3 Correct 732 ms 82448 KB Output is correct
4 Correct 631 ms 77292 KB Output is correct
5 Correct 531 ms 69528 KB Output is correct
6 Correct 740 ms 86176 KB Output is correct
7 Correct 792 ms 84432 KB Output is correct
8 Correct 789 ms 83788 KB Output is correct
9 Correct 765 ms 77568 KB Output is correct
10 Correct 659 ms 77460 KB Output is correct
11 Correct 527 ms 79460 KB Output is correct
12 Correct 474 ms 84224 KB Output is correct
13 Correct 513 ms 86388 KB Output is correct
14 Correct 475 ms 81352 KB Output is correct
15 Correct 80 ms 23120 KB Output is correct
16 Correct 684 ms 72564 KB Output is correct
17 Correct 536 ms 69932 KB Output is correct
18 Correct 632 ms 65740 KB Output is correct
19 Correct 730 ms 81636 KB Output is correct
20 Correct 808 ms 83040 KB Output is correct
21 Correct 722 ms 77720 KB Output is correct
22 Correct 614 ms 78052 KB Output is correct