oj.uz

Submission #412057

# Submission time Handle Problem Language Result Execution time Memory
412057 2021-05-26T12:50:40 Z 송준혁(#7508) Pastiri (COI20_pastiri) C++17
8 / 100
 720 ms 46736 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];
bool chk[505050], vis[505050];
queue<int> Q;
vector<int> adj[505050], ans;

void del(int u){
	vis[u] = true;
	for (int v : adj[u]) if (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);
		D[u]++, D[v]++;
	}
	memset(A, -1, sizeof A);
	for (int i=1; i<=K; i++){
		int x;
		scanf("%d", &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);
		}
	}
	for (int i=1; i<=N; i++) if (D[i] == 1) Q.push(i);
	while (Q.size()){
		int u = Q.front(); Q.pop();
		for (int v : adj[u]){
			D[v]--;
			if (D[v] == 1) Q.push(v);
		}
		if (vis[u] || !chk[u]){
			vis[u] = true;
			continue;
		}
		bool tf = true;
		while (tf){
			tf = false;
			for (int v : adj[u]){
				if (!vis[v] && A[v] == A[u]+1){
					u = v, tf = true;
					break;
				}
			}
		}
		ans.pb(u);
		del(u);
	}
	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:73:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   73 |  printf("%d\n", ans.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<int>::size_type {aka long unsigned int}
      |          %ld
pastiri.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d %d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 46736 KB Output is correct
2 Correct 239 ms 32764 KB Output is correct
3 Correct 262 ms 35128 KB Output is correct
4 Correct 331 ms 38780 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 14340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 720 ms 33688 KB Output isn't correct
2 Halted 0 ms 0 KB -