oj.uz

Submission #1003815

# Submission time Handle Problem Language Result Execution time Memory
1003815 2024-06-20T18:20:15 Z vjudge1 Pastiri (COI20_pastiri) C++17
100 / 100
 558 ms 179964 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;
int lazy[maxn];

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));
		if(st[v].size() < st[u].size()) {
			for(auto x : st[v]) st[u].insert(x-1+lazy[v]-lazy[u]);
		}
		else {
			lazy[v]--;
			for(auto x : st[u]) st[v].insert(x-lazy[v]+lazy[u]);
			lazy[u] = 0;
			swap(st[u],st[v]);
			swap(lazy[u],lazy[v]);
		}
	}


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

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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 156752 KB Output is correct
2 Correct 345 ms 163412 KB Output is correct
3 Correct 312 ms 163616 KB Output is correct
4 Correct 437 ms 179964 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35932 KB Output is correct
2 Correct 16 ms 35932 KB Output is correct
3 Correct 477 ms 71912 KB Output is correct
4 Correct 400 ms 76844 KB Output is correct
5 Correct 472 ms 68688 KB Output is correct
6 Correct 478 ms 76928 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35676 KB Output is correct
2 Correct 14 ms 35640 KB Output is correct
3 Correct 14 ms 35676 KB Output is correct
4 Correct 13 ms 35672 KB Output is correct
5 Correct 14 ms 35676 KB Output is correct
6 Correct 14 ms 35676 KB Output is correct
7 Correct 15 ms 35676 KB Output is correct
8 Correct 15 ms 35676 KB Output is correct
9 Correct 15 ms 35672 KB Output is correct
10 Correct 15 ms 35676 KB Output is correct
11 Correct 15 ms 35820 KB Output is correct
12 Correct 15 ms 35676 KB Output is correct
13 Correct 16 ms 35672 KB Output is correct
14 Correct 18 ms 35932 KB Output is correct
15 Correct 18 ms 35676 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 67920 KB Output is correct
2 Correct 483 ms 74324 KB Output is correct
3 Correct 495 ms 78828 KB Output is correct
4 Correct 489 ms 69704 KB Output is correct
5 Correct 357 ms 71944 KB Output is correct
6 Correct 481 ms 88776 KB Output is correct
7 Correct 485 ms 82760 KB Output is correct
8 Correct 464 ms 82464 KB Output is correct
9 Correct 445 ms 69972 KB Output is correct
10 Correct 438 ms 69964 KB Output is correct
11 Correct 448 ms 75536 KB Output is correct
12 Correct 379 ms 78000 KB Output is correct
13 Correct 469 ms 80232 KB Output is correct
14 Correct 363 ms 76576 KB Output is correct
15 Correct 57 ms 41552 KB Output is correct
16 Correct 409 ms 67728 KB Output is correct
17 Correct 330 ms 72636 KB Output is correct
18 Correct 387 ms 63568 KB Output is correct
19 Correct 486 ms 87844 KB Output is correct
20 Correct 558 ms 99404 KB Output is correct
21 Correct 434 ms 72272 KB Output is correct
22 Correct 461 ms 74064 KB Output is correct