oj.uz

Submission #773961

# Submission time Handle Problem Language Result Execution time Memory
773961 2023-07-05T10:03:44 Z vjudge1 Pastiri (COI20_pastiri) C++17
100 / 100
 854 ms 168196 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 162648 KB Output is correct
2 Correct 256 ms 165412 KB Output is correct
3 Correct 250 ms 165644 KB Output is correct
4 Correct 314 ms 168196 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24148 KB Output is correct
2 Correct 15 ms 24164 KB Output is correct
3 Correct 440 ms 57236 KB Output is correct
4 Correct 435 ms 57828 KB Output is correct
5 Correct 584 ms 67864 KB Output is correct
6 Correct 594 ms 76904 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 13 ms 23996 KB Output is correct
3 Correct 13 ms 23944 KB Output is correct
4 Correct 12 ms 23904 KB Output is correct
5 Correct 11 ms 24020 KB Output is correct
6 Correct 12 ms 23948 KB Output is correct
7 Correct 12 ms 23952 KB Output is correct
8 Correct 12 ms 24004 KB Output is correct
9 Correct 11 ms 23892 KB Output is correct
10 Correct 12 ms 23964 KB Output is correct
11 Correct 12 ms 23960 KB Output is correct
12 Correct 11 ms 23892 KB Output is correct
13 Correct 11 ms 23952 KB Output is correct
14 Correct 12 ms 24088 KB Output is correct
15 Correct 14 ms 24020 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 61280 KB Output is correct
2 Correct 648 ms 67532 KB Output is correct
3 Correct 586 ms 68000 KB Output is correct
4 Correct 529 ms 71288 KB Output is correct
5 Correct 344 ms 62424 KB Output is correct
6 Correct 502 ms 78980 KB Output is correct
7 Correct 580 ms 74772 KB Output is correct
8 Correct 584 ms 76240 KB Output is correct
9 Correct 612 ms 71204 KB Output is correct
10 Correct 538 ms 68104 KB Output is correct
11 Correct 428 ms 61072 KB Output is correct
12 Correct 339 ms 62440 KB Output is correct
13 Correct 347 ms 64508 KB Output is correct
14 Correct 381 ms 59588 KB Output is correct
15 Correct 50 ms 30812 KB Output is correct
16 Correct 481 ms 67388 KB Output is correct
17 Correct 301 ms 60220 KB Output is correct
18 Correct 463 ms 62628 KB Output is correct
19 Correct 767 ms 80832 KB Output is correct
20 Correct 854 ms 95148 KB Output is correct
21 Correct 746 ms 63728 KB Output is correct
22 Correct 604 ms 65976 KB Output is correct