oj.uz

Submission #412072

# Submission time Handle Problem Language Result Execution time Memory
412072 2021-05-26T13:20:53 Z 송준혁(#7508) Pastiri (COI20_pastiri) C++17
100 / 100
 791 ms 54436 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, K;
int A[505050], D[505050], dep[505050];
bool chk[505050], vis[505050];
queue<int> Q;
vector<int> adj[505050], ans, P;

void dfs(int u, int p){
	for (int v : adj[u]){
		if (v == p) continue;
		dep[v] = dep[u] + 1;
		dfs(v, u);
	}
}

void del(int u){
	vis[u] = true;
	for (int v : adj[u]) if (!vis[v] && A[v] == A[u]-1) del(v);
}

int main(){
	scanf("%d %d", &N, &K);
	if (N==1){
		puts("1\n1");
		return 0;
	}
	for (int i=1; i<N; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].pb(v), adj[v].pb(u);
	}
	memset(A, -1, sizeof A);
	for (int i=1; i<=K; i++){
		int x;
		scanf("%d", &x);
		P.pb(x);
		chk[x] = true, Q.push(x), A[x] = 0;
	}
	while (Q.size()){
		int u = Q.front(); Q.pop();
		for (int v : adj[u]){
			if (A[v]>=0) continue;
			A[v] = A[u]+1;
			Q.push(v);
		}
	}
	dfs(1, 0);
	sort(P.begin(), P.end(), [&](int a, int b){return dep[a] > dep[b];});
	for (int u : P){
		if (vis[u]) continue;
		bool tf = true;
		int c = u;
		while (tf){
			tf = false;
			for (int v : adj[c]){
				if (A[v] == A[c]+1 && dep[v] < dep[c]){
					c = v, tf = true;
					break;
				}
			}
		}
		ans.pb(c);
		del(c);
	}
	printf("%d\n", ans.size());
	for (int u : ans) printf("%d ", u);
	printf("\n");
	return 0;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:75:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   75 |  printf("%d\n", ans.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<int>::size_type {aka long unsigned int}
      |          %ld
pastiri.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d %d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 48384 KB Output is correct
2 Correct 267 ms 49256 KB Output is correct
3 Correct 242 ms 49204 KB Output is correct
4 Correct 360 ms 54436 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14284 KB Output is correct
2 Correct 15 ms 14284 KB Output is correct
3 Correct 537 ms 32616 KB Output is correct
4 Correct 512 ms 34988 KB Output is correct
5 Correct 592 ms 32324 KB Output is correct
6 Correct 784 ms 33856 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14156 KB Output is correct
2 Correct 10 ms 14140 KB Output is correct
3 Correct 10 ms 14156 KB Output is correct
4 Correct 9 ms 14156 KB Output is correct
5 Correct 11 ms 14156 KB Output is correct
6 Correct 11 ms 14200 KB Output is correct
7 Correct 10 ms 14204 KB Output is correct
8 Correct 10 ms 14156 KB Output is correct
9 Correct 10 ms 14240 KB Output is correct
10 Correct 10 ms 14144 KB Output is correct
11 Correct 10 ms 14128 KB Output is correct
12 Correct 9 ms 14156 KB Output is correct
13 Correct 10 ms 14156 KB Output is correct
14 Correct 10 ms 14240 KB Output is correct
15 Correct 10 ms 14228 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 33532 KB Output is correct
2 Correct 577 ms 33280 KB Output is correct
3 Correct 702 ms 36060 KB Output is correct
4 Correct 581 ms 32688 KB Output is correct
5 Correct 528 ms 32120 KB Output is correct
6 Correct 715 ms 38384 KB Output is correct
7 Correct 757 ms 37384 KB Output is correct
8 Correct 763 ms 37060 KB Output is correct
9 Correct 791 ms 32816 KB Output is correct
10 Correct 592 ms 32360 KB Output is correct
11 Correct 518 ms 34680 KB Output is correct
12 Correct 459 ms 37404 KB Output is correct
13 Correct 482 ms 38576 KB Output is correct
14 Correct 494 ms 36320 KB Output is correct
15 Correct 64 ms 17348 KB Output is correct
16 Correct 650 ms 31528 KB Output is correct
17 Correct 514 ms 39056 KB Output is correct
18 Correct 580 ms 34824 KB Output is correct
19 Correct 658 ms 43336 KB Output is correct
20 Correct 713 ms 44688 KB Output is correct
21 Correct 548 ms 39544 KB Output is correct
22 Correct 559 ms 39800 KB Output is correct