oj.uz

Submission #759616

# Submission time Handle Problem Language Result Execution time Memory
759616 2023-06-16T13:19:21 Z NintsiChkhaidze Pastiri (COI20_pastiri) C++17
100 / 100
 436 ms 92824 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair <int,int>
#define left (h<<1),l,((l + r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int N = 5e5 + 5,inf = 1e9;

int dis[N],d[N],m[N];
bool vis[N];
vector <int> v[N],ans;

void dfs(int x,int par){

	d[x] = m[x] = -inf;
	if (dis[x] == 0) d[x] = 0;
	
	for (int to: v[x]){
		if (to == par) continue;
		dfs(to,x);
		
		if (d[to] + 1 > dis[x]){
			ans.pb(to);
			d[to] = -inf;
			m[to] = dis[to];
		}

		m[x] = max(m[x],m[to] - 1);
		d[x] = max(d[x],d[to] + 1);
	}

	if (m[x] >= d[x]) d[x] = -inf;
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,m;
	cin>>n>>m;

	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	
	for (int i = 1; i <= n; i++) 	
		dis[i] = inf;

	queue <int> q;
	for (int i = 1; i <= m; i++){
		int x;
		cin>>x;
		dis[x] = 0;
		q.push(x);
	}

	while (q.size()){
		int x = q.front();
		q.pop();
		for (int to: v[x]){
			if (dis[to] > dis[x] + 1){
				dis[to] = dis[x] + 1;
				q.push(to);
			}
		}
	}

	dfs(1,1);
	if (d[1] != -inf) ans.pb(1);
	cout<<ans.size()<<"\n";
	sort(ans.begin(),ans.end());
	for (int x: ans) cout<<x<<" ";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 80536 KB Output is correct
2 Correct 159 ms 80504 KB Output is correct
3 Correct 171 ms 80596 KB Output is correct
4 Correct 205 ms 92824 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Correct 374 ms 34012 KB Output is correct
4 Correct 363 ms 36428 KB Output is correct
5 Correct 413 ms 33708 KB Output is correct
6 Correct 413 ms 37800 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12156 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 6 ms 12168 KB Output is correct
4 Correct 7 ms 12176 KB Output is correct
5 Correct 8 ms 12216 KB Output is correct
6 Correct 7 ms 12212 KB Output is correct
7 Correct 7 ms 12088 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 6 ms 12116 KB Output is correct
12 Correct 6 ms 12080 KB Output is correct
13 Correct 6 ms 12116 KB Output is correct
14 Correct 9 ms 12264 KB Output is correct
15 Correct 7 ms 12164 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 34744 KB Output is correct
2 Correct 381 ms 34632 KB Output is correct
3 Correct 395 ms 43668 KB Output is correct
4 Correct 414 ms 40224 KB Output is correct
5 Correct 287 ms 38212 KB Output is correct
6 Correct 418 ms 49504 KB Output is correct
7 Correct 384 ms 47212 KB Output is correct
8 Correct 410 ms 46804 KB Output is correct
9 Correct 432 ms 40312 KB Output is correct
10 Correct 429 ms 40320 KB Output is correct
11 Correct 299 ms 42256 KB Output is correct
12 Correct 259 ms 45184 KB Output is correct
13 Correct 311 ms 46872 KB Output is correct
14 Correct 246 ms 43796 KB Output is correct
15 Correct 31 ms 16716 KB Output is correct
16 Correct 391 ms 38260 KB Output is correct
17 Correct 313 ms 38552 KB Output is correct
18 Correct 323 ms 35164 KB Output is correct
19 Correct 436 ms 47940 KB Output is correct
20 Correct 428 ms 53804 KB Output is correct
21 Correct 399 ms 40324 KB Output is correct
22 Correct 392 ms 41196 KB Output is correct