oj.uz

Submission #759609

# Submission time Handle Problem Language Result Execution time Memory
759609 2023-06-16T13:08:22 Z NintsiChkhaidze Pastiri (COI20_pastiri) C++17
18 / 100
 497 ms 81408 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();
		vis[x] = 1;
		for (int to: v[x]){
			if (!vis[to]){
				vis[to] = 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 81408 KB Output is correct
2 Correct 156 ms 81408 KB Output is correct
3 Incorrect 160 ms 81332 KB Sheep 80212 not protected
4 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12368 KB Output is correct
2 Correct 7 ms 12344 KB Output is correct
3 Correct 342 ms 34908 KB Output is correct
4 Correct 325 ms 37264 KB Output is correct
5 Correct 484 ms 34488 KB Output is correct
6 Correct 497 ms 38576 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Incorrect 7 ms 12176 KB Sheep 63 not protected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 35540 KB Output is correct
2 Incorrect 392 ms 35276 KB Sheep 438733 not protected
3 Halted 0 ms 0 KB -