Submission #773961

#	Time	Username	Problem	Language	Result	Execution time	Memory
773961		vjudge1	Pastiri (COI20_pastiri)	C++17	100 / 100	854 ms	168196 KiB

pastiri

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 500005


const int modulo = 1e9 + 7;

int flag[N], dep[N], maks[N], up[N], mark[N];
vector<int> child[N], adj[N];

void dfs(int node, int root, int d){
	dep[node] = d;
	for (auto i : adj[node]){
		if (i == root) continue;
		child[node].pb(i);
		dfs(i, node, d + 1);
	}
}


void dfs2(int node){
	maks[node] = modulo;
	if (mark[node]) maks[node] = 0;
	for (auto i : child[node])
	{
		dfs2(i);
		maks[node] = min(maks[node], maks[i] + 1);
	}
	//cout<<node<<sp<<maks[node]<<endl;
}

void dfs3(int node, int val){
	vector<int> pre, suf;
	up[node] = val;
	//cout<<"! "<<node<<sp<<val<<endl;
	if (mark[node]) val = 0;
	pre.pb(modulo);
	for (int i = 0; i < (int)child[node].size() - 1; i++)
	{
		pre.pb(min(maks[child[node][i]], pre.back()));
	}
	suf.pb(modulo);
	for (int i = (int)child[node].size() - 1; i > 0; i--)
	{
		suf.pb(min(maks[child[node][i]], suf.back()));
	}
	reverse(suf.begin(), suf.end());
	for (int i = 0; i < child[node].size(); i++)
		dfs3(child[node][i], min(val, min(pre[i], suf[i]) + 1) + 1);
}


pii dfs4(int node){
	int curr = modulo, dist = 0;
	for (auto i : child[node]) 
	{
		pii tmp = dfs4(i);
		curr = min(curr, tmp.st + 1);
		dist = max(dist, tmp.nd);
	}
	if (dist == 0 && mark[node]) curr = 0;
	if (dist > curr) curr = modulo;
	//cout<<node<<sp<<dist<<sp<<curr<<sp<<up[node]<<endl;
	dist--;
	if (curr != modulo && (abs(up[node] - curr) <= 1 || node == 1))
	{
		flag[node] = 1;
		dist = curr;
		curr = modulo;
	}
	return make_pair(curr, dist);
}


int32_t main(){
	//fileio();
	fastio();


	int n, k;
	cin>>n>>k;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}


	for (int i = 1; i <= k; i++){
		int tmp;
		cin>>tmp;
		mark[tmp] = 1;
	}

	dfs(1, 0, 1);
	dfs2(1);
	dfs3(1, modulo);
	
	pii tmp = dfs4(1);

	vector<int> v;
	for (int i = 1; i <= n; i++)
		if (flag[i]) v.pb(i);
	sort(v.begin(), v.end());
	cout<<v.size()<<endl;
	for (auto i : v)
		cout<<i<<sp;
	cout<<endl;



	//cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Compilation message (stderr)

pastiri.cpp: In function 'void dfs3(int, int)':
pastiri.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < child[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~
pastiri.cpp: In function 'int32_t main()':
pastiri.cpp:109:6: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
  109 |  pii tmp = dfs4(1);
      |      ^~~

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