Submission #745387

#	Time	Username	Problem	Language	Result	Execution time	Memory
745387		nvujica	Pastiri (COI20_pastiri)	C++14	0 / 100	370 ms	213368 KiB

pastiri

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 5e5 + 10;

int n, k;
int ovca[maxn];
int d[maxn];
int u[maxn];
vector <int> v[maxn];
int dp[maxn][3];
int sta[maxn][3];
vector <int> ans;

int rek(int x, int p){
	if(ovca[x]) d[x] = 0;
	else d[x] = maxn;
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(x2 == p) continue;
		
		d[x] = min(d[x], rek(x2, x) + 1);
	}
	
	return d[x];
}

int rek2(int x, int p){
	if(ovca[x]) u[x] = 0;
	
	vector <int> t;
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(x2 == p) continue;
		
		t.push_back(d[x2]);
	}
	
	t.push_back(maxn);
	
	sort(t.begin(), t.end());
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(x2 == p) continue;
		
		if(d[x2] == t[0]) u[x2] = min(u[x] + 1, t[1] + 2);
		else u[x2] = min(u[x] + 1, t[0] + 2);
		
		rek2(x2, x);
	}
}

void rek3(int x, int p){
	dp[x][0] = maxn;
	dp[x][1] = maxn;
	dp[x][2] = maxn;
	
	ll sum = 0;
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(x2 == p) continue;
		
		rek3(x2, x);
		
		sum += dp[x2][0];
	}
	
	if(ovca[x]){
		int naj = maxn + 1, y;
	
		for(int i = 0; i < v[x].size(); i++){
			int x2 = v[x][i];
		
			if(x2 == p) continue;
		
			if(dp[x2][1] - dp[x2][0] < naj){
				naj = dp[x2][1] - dp[x2][0];
				y = x2;
			}
//			naj = min(naj, dp[x2][1] - dp[x2][0]);	
		}
		
		if(naj < 1){
			sta[x][0] = y;
		}
		else {
			sta[x][0] = x;
		}
		dp[x][0] = sum + min(naj, 1);
		dp[x][2] = sum;
		
		return;
	}
	
	dp[x][0] = min((ll)dp[x][0], sum);
	
	ll sum2 = 0;
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
	
		if(x2 == p) continue;
	
		if(d[x2] + 1 == d[x]) sum2 += dp[x2][2];
		else sum2 += dp[x2][0];
	}
	
	dp[x][2] = sum2;
	
	if(d[x] <= u[x]){
		ll sum3 = 0;
		int naj = maxn + 1, y;
		
		for(int i = 0; i < v[x].size(); i++){
			int x2 = v[x][i];
		
			if(x2 == p) continue;
		
			if(d[x2] + 1 == d[x]){
				sum3 += dp[x2][2];
				if(dp[x2][1] - dp[x2][2] < naj){
					naj = dp[x2][1] - dp[x2][2];
					y = x2;
				}
//				naj = min(naj, dp[x2][1] - dp[x2][2]);
			}
			else {
				sum3 += dp[x2][0];
				if(dp[x2][1] - dp[x2][0] < naj){
					naj = dp[x2][1] - dp[x2][0];
					y = x2;
				}
//				naj = min(naj, dp[x2][1] - dp[x2][0]);
			}
		}
		
		if(sum3 + min(naj, 1) < dp[x][0]){
			dp[x][0] = sum3 + min(naj, 1);
			if(naj < 1) sta[x][0] = y;
			else sta[x][0] = x; 
		}
		
//		dp[x][0] = min((ll)dp[x][0], sum3 + min(naj, 1));
	
		if(d[x] == u[x]){
			if(sum3 + min(naj, 1) < dp[x][1]){
				dp[x][1] = sum3 + min(naj, 1);
				if(naj < 1) sta[x][1] = y;
				else sta[x][1] = x; 
			}
			
//			dp[x][1] = min((ll)dp[x][1], sum3 + min(naj, 1));
		}
	}
	else {
		int naj = maxn + 1, y;
		
		for(int i = 0; i < v[x].size(); i++){
			int x2 = v[x][i];
		
			if(x2 == p) continue;
		
			if(dp[x2][1] - dp[x2][0] < naj){
				naj = dp[x2][1] - dp[x2][0];
				y = x2;
			}
//			naj = min(naj, dp[x2][1] - dp[x2][0]);
		}
		
		if(sum + min(naj, 1) < dp[x][1]){
			dp[x][1] = sum + min(naj, 1);
			if(naj < 1) sta[x][1] = y;
			else sta[x][1] = x; 
		}
//		dp[x][1] = min((ll)dp[x][1], sum + min(naj, 1));
	}
}

void rek4(int x, int p, int b){
//		cout << x << ' ' << b << endl;
	
	if(sta[x][b] == x) ans.push_back(x);
	
	if(ovca[x]){				
		for(int i = 0; i < v[x].size(); i++){
			int x2 = v[x][i];
			
			if(x2 == p) continue;
			
			if(sta[x][b] == x2) rek4(x2, x, 1);
			else rek4(x2, x, 0);
		}
		return;
	}
	
	if(b == 0 && sta[x][0] == 0){
		for(int i = 0; i < v[x].size(); i++){
			int x2 = v[x][i];
			
			if(x2 == p) continue;
			
			rek4(x2, x, 0);
		}
		return;
	}
	
	if(b == 2){
		for(int i = 0; i < v[x].size(); i++){
			int x2 = v[x][i];
		
			if(x2 == p) continue;
		
			if(d[x2] + 1 == d[x]) rek4(x2, x, 2);
			else rek4(x2, x, 0);
		}
		
		return;
	}
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(x2 == p) continue;
		
		if(sta[x][b] == x2) rek4(x2, x, 1);
		else {
			if(d[x] <= u[x] && d[x2] + 1 == d[x]) rek4(x2, x, 2);
			else rek4(x2, x, 0);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	
	for(int i = 0; i < n - 1; i++){
		int a, b;
		cin >> a >> b;
		
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	for(int i = 0; i < k; i++){
		int a;
		cin >> a;
		ovca[a] = 1;
	}
	
	rek(1, 0);
	u[1] = maxn;
	rek2(1, 0);
	
//	for(int i = 1; i <= n; i++){
//		cout << i << ' ' << u[i] << endl;
//	}

	rek3(1, 0);
	rek4(1, 0, 0);
	
	cout << dp[1][0] << "\n";
	
	sort(ans.begin(), ans.end());
	
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i] << ' ';
	}
	
	return 0;
}

Compilation message (stderr)

pastiri.cpp: In function 'int rek(int, int)':
pastiri.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
pastiri.cpp: In function 'int rek2(int, int)':
pastiri.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
pastiri.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
pastiri.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
   62 | }
      | ^
pastiri.cpp: In function 'void rek3(int, int)':
pastiri.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
pastiri.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
pastiri.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
pastiri.cpp:127:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for(int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
pastiri.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   for(int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
pastiri.cpp: In function 'void rek4(int, int, int)':
pastiri.cpp:198:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |   for(int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
pastiri.cpp:210:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |   for(int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
pastiri.cpp:221:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |   for(int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
pastiri.cpp:233:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
pastiri.cpp: In function 'int main()':
pastiri.cpp:281:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  281 |  for(int i = 0; i < ans.size(); i++){
      |                 ~~^~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 18
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51