oj.uz

Submission #759590

# Submission time Handle Problem Language Result Execution time Memory
759590 2023-06-16T12:48:46 Z NintsiChkhaidze Pastiri (COI20_pastiri) C++17
18 / 100
 512 ms 80316 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 fix[N],vis[N];
vector <int> v[N];

void dfs(int x,int par){

	d[x] = m[x] = -inf;
	if (fix[x]) {
		d[x] = 0;
	}
	
	for (int to: v[x]){
		if (to == par) continue;
		dfs(to,x);
		
		if (d[to] + 1 > dis[x]){
			//to-shi uechveli unda dasva cxvari
			d[to] = 0;
			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;
		fix[x] = 1;
		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) d[1] = 0;
	vector <int> ans;
	for (int i = 1; i <= n; i++){
		if (dis[i] != 0 && d[i] == 0){
			ans.pb(i);
		}
	}

	cout<<ans.size()<<"\n";
	for (int x: ans) cout<<x<<" ";
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 74884 KB Output is correct
2 Correct 164 ms 80252 KB Output is correct
3 Incorrect 163 ms 80316 KB Sheep 79145 not protected
4 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 7 ms 12372 KB Output is correct
3 Correct 374 ms 41288 KB Output is correct
4 Correct 339 ms 43568 KB Output is correct
5 Correct 435 ms 40852 KB Output is correct
6 Correct 504 ms 44296 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 512 ms 42276 KB Output isn't correct
2 Halted 0 ms 0 KB -