oj.uz

Submission #1003813

# Submission time Handle Problem Language Result Execution time Memory
1003813 2024-06-20T18:19:28 Z vjudge1 Pastiri (COI20_pastiri) C++17
41 / 100
 942 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int maxn = 5e5+10;
const int inf = 1e18+10;

int n, k, down[maxn], dist[maxn];
vector<int> g[maxn];
set<int> st[maxn];
int ans;
vector<int> ansv;

void dfs(int u, int ant) {
	down[u] = -1;
	if(dist[u] == 0) down[u] = 0;
	vector<pair<int,int>> ord;
	for(auto v : g[u]) if(v != ant) {
		dfs(v,u);
		ord.pb(mp(down[v],v));
		for(auto x : st[v]) st[u].insert(x-1);
	}

	sort(all(ord),greater<pair<int,int>>());


	for(auto V : ord) {
		int v = V.sc;
		// cout << " " << v << " " << down[v] << " " << st[u].count(1) << endl;
		if(down[v] != -1 && st[u].count(down[v]+1) == 0) {
			if(dist[u] != down[v]+1) {
				// cout << " coloca em " << v << endl;
				ansv.pb(v);
				ans++;
				st[u].insert(dist[v]-1);
				down[v] = -1;
			}
			else {
				down[u] = down[v]+1;
			}
		}
	}
	// cout << u << " " << down[u] << " " << dist[u] << " " << ans << " " << st[u].count(1) << endl;
	if(down[u] != -1) {
		if(st[u].count(down[u])) {
			down[u] = -1;
		}
	}
	// cout << u << " " << down[u] << " " << dist[u] << " " << ans << " " << st[u].count(1) << endl;
}

int32_t main() {
	// #ifndef ONLINE_JUDGE
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	// #endif

	cin >> n >> k;
	for(int i = 1; i <= n-1; i++) {
		int u,v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}

	queue<int> q;
	for(int i = 1; i <= n; i++) {
		dist[i] = inf;
	}

	for(int i = 0; i < k; i++) {
		int x;
		cin >> x;
		dist[x] = 0;
		q.push(x);
	}
	while(q.size()) {
		int u = q.front();
		q.pop();
		for(auto v : g[u]) {
			if(dist[v] == inf) {
				q.push(v);
				dist[v] = dist[u]+1;
			}
		}
	}

	int r = 1;
	dfs(r,0);
	if(down[r] != -1) ansv.pb(r);
	cout << ansv.size() << endl;
	for(auto x : ansv) cout << x << " ";
	cout << endl;
	// cout << ans + (down[1] != -1) << endl;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 137244 KB Output is correct
2 Runtime error 628 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35932 KB Output is correct
2 Correct 16 ms 35808 KB Output is correct
3 Correct 419 ms 69096 KB Output is correct
4 Correct 413 ms 74028 KB Output is correct
5 Correct 468 ms 66132 KB Output is correct
6 Correct 526 ms 73388 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35676 KB Output is correct
2 Correct 16 ms 35672 KB Output is correct
3 Correct 19 ms 35676 KB Output is correct
4 Correct 16 ms 35676 KB Output is correct
5 Correct 18 ms 36896 KB Output is correct
6 Correct 17 ms 35676 KB Output is correct
7 Correct 16 ms 35676 KB Output is correct
8 Correct 16 ms 35676 KB Output is correct
9 Correct 16 ms 35660 KB Output is correct
10 Correct 15 ms 35676 KB Output is correct
11 Correct 17 ms 35672 KB Output is correct
12 Correct 16 ms 35692 KB Output is correct
13 Correct 16 ms 35616 KB Output is correct
14 Correct 25 ms 40028 KB Output is correct
15 Correct 17 ms 36188 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 942 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -