oj.uz

Submission #367751

# Submission time Handle Problem Language Result Execution time Memory
367751 2021-02-18T09:01:21 Z arnold518 Pastiri (COI20_pastiri) C++14
100 / 100
 897 ms 87380 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;
const int MAXK = 5e5;
const int INF = 987654321;

int N, K;
vector<int> adj[MAXN+10];

int P[MAXN+10];

int dep[MAXN+10], par[MAXN+10];
int dp[MAXN+10], dp2[MAXN+10];

void dfs(int now, int bef, int d)
{
	dep[now]=d;
	par[now]=bef;
	dp[now]=INF;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
		dp[now]=min(dp[now], dp[nxt]+1);
	}
	if(P[now]) dp[now]=0;
}

void dfs2(int now, int bef)
{
	int p=INF;
	for(int i=0; i<adj[now].size(); i++)
	{
		int nxt=adj[now][i];
		if(nxt==bef) continue;
		dp2[nxt]=min(dp2[nxt], p);
		p=min(p, dp[nxt]+1);
	}
	p=INF;
	for(int i=adj[now].size()-1; i>=0; i--)
	{
		int nxt=adj[now][i];
		if(nxt==bef) continue;
		dp2[nxt]=min(dp2[nxt], p);
		p=min(p, dp[nxt]+1);
	}
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dp2[nxt]=min(dp2[nxt], dp2[now]+1);
	}
	if(P[now])
	{
		for(int nxt : adj[now])
		{
			if(nxt==bef) continue;
			dp2[nxt]=0;
		}
	}
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs2(nxt, now);
	}
}

struct Data
{
	int u, du, dv;
	bool operator < (const Data &p) const
	{
		return du<p.du;
	}
};

int L[MAXN+10];

bool vis[MAXN+10];
int main()
{
	scanf("%d%d", &N, &K);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vector<int> VV;
	for(int i=0; i<K; i++)
	{
		int t;
		scanf("%d", &t);
		VV.push_back(t);
		P[t]=1;
	}

	dfs(1, 1, 1);
	for(int i=1; i<=N; i++) dp2[i]=INF;
	dfs2(1, 1);

	//for(int i=1; i<=N; i++) printf("%d ", dp2[i]); printf("\n");

	priority_queue<Data> PQ;
	for(auto it : VV)
	{
		PQ.push({it, dep[it], dep[it],});
		vis[it]=true;
	}
	vector<int> ans;
	memset(L, -1, sizeof(L));
	while(!PQ.empty())
	{
		Data now=PQ.top(); PQ.pop();
		//printf("PQ %d %d %d %d\n", now.u, now.du, now.dv, L[now.u]);
		if(now.dv-dep[now.u]<=L[now.u]) continue;
		if(now.u==1 || dp2[now.u]<now.dv-dep[par[now.u]])
		{
			ans.push_back(now.u);
			//printf("FIX %d\n", now.u);
			int p=now.u, k=now.dv-dep[now.u];
			for(int i=k-1; i>=0; i--)
			{
				p=par[p];
				//printf("%d %d\n", p, i);
				L[p]=max(L[p], i);
				if(p==1) break;
			}
		}
		else if(!vis[par[now.u]])
		{
			vis[par[now.u]]=true;
			PQ.push({par[now.u], dep[par[now.u]], now.dv});
		}
	}
	printf("%d\n", ans.size());
	for(auto it : ans) printf("%d ", it); printf("\n");
}

Compilation message

pastiri.cpp: In function 'void dfs2(int, int)':
pastiri.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0; i<adj[now].size(); i++)
      |               ~^~~~~~~~~~~~~~~~
pastiri.cpp: In function 'int main()':
pastiri.cpp:141:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  141 |  printf("%d\n", ans.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<int>::size_type {aka long unsigned int}
      |          %ld
pastiri.cpp:142:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  142 |  for(auto it : ans) printf("%d ", it); printf("\n");
      |  ^~~
pastiri.cpp:142:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  142 |  for(auto it : ans) printf("%d ", it); printf("\n");
      |                                        ^~~~~~
pastiri.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
pastiri.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
pastiri.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 76928 KB Output is correct
2 Correct 239 ms 78700 KB Output is correct
3 Correct 245 ms 78700 KB Output is correct
4 Correct 406 ms 87380 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14316 KB Output is correct
2 Correct 12 ms 14316 KB Output is correct
3 Correct 606 ms 37868 KB Output is correct
4 Correct 575 ms 40400 KB Output is correct
5 Correct 692 ms 38272 KB Output is correct
6 Correct 781 ms 41608 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14188 KB Output is correct
2 Correct 13 ms 14188 KB Output is correct
3 Correct 12 ms 14188 KB Output is correct
4 Correct 11 ms 14188 KB Output is correct
5 Correct 12 ms 14316 KB Output is correct
6 Correct 13 ms 14188 KB Output is correct
7 Correct 10 ms 14188 KB Output is correct
8 Correct 12 ms 14336 KB Output is correct
9 Correct 11 ms 14188 KB Output is correct
10 Correct 11 ms 14188 KB Output is correct
11 Correct 11 ms 14188 KB Output is correct
12 Correct 10 ms 14188 KB Output is correct
13 Correct 11 ms 14188 KB Output is correct
14 Correct 11 ms 14316 KB Output is correct
15 Correct 11 ms 14188 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 41436 KB Output is correct
2 Correct 674 ms 47984 KB Output is correct
3 Correct 822 ms 52976 KB Output is correct
4 Correct 719 ms 46708 KB Output is correct
5 Correct 617 ms 46556 KB Output is correct
6 Correct 894 ms 60888 KB Output is correct
7 Correct 893 ms 56280 KB Output is correct
8 Correct 897 ms 55512 KB Output is correct
9 Correct 793 ms 46700 KB Output is correct
10 Correct 685 ms 45036 KB Output is correct
11 Correct 554 ms 48476 KB Output is correct
12 Correct 534 ms 54620 KB Output is correct
13 Correct 607 ms 59096 KB Output is correct
14 Correct 464 ms 49388 KB Output is correct
15 Correct 85 ms 20008 KB Output is correct
16 Correct 723 ms 44840 KB Output is correct
17 Correct 602 ms 47100 KB Output is correct
18 Correct 650 ms 40812 KB Output is correct
19 Correct 740 ms 54492 KB Output is correct
20 Correct 739 ms 58884 KB Output is correct
21 Correct 650 ms 46572 KB Output is correct
22 Correct 668 ms 47340 KB Output is correct