oj.uz

Submission #759593

# Submission time Handle Problem Language Result Execution time Memory
759593 2023-06-16T12:57:24 Z NintsiChkhaidze Pastiri (COI20_pastiri) C++17
18 / 100
 495 ms 82424 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],ans;

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
			ans.pb(to);
			d[to] = -inf;
			m[to] = max(dis[to],m[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) ans.pb(1);
	cout<<ans.size()<<"\n";
	for (int x: ans) cout<<x<<" ";
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 80992 KB Output is correct
2 Correct 158 ms 81408 KB Output is correct
3 Incorrect 191 ms 82424 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 7 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 371 ms 35680 KB Output is correct
4 Correct 329 ms 37780 KB Output is correct
5 Correct 465 ms 34864 KB Output is correct
6 Correct 495 ms 39076 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 6 ms 12116 KB Sheep 63 not protected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 35704 KB Output is correct
2 Incorrect 411 ms 42196 KB Sheep 438733 not protected
3 Halted 0 ms 0 KB -