oj.uz

Submission #412070

# Submission time Handle Problem Language Result Execution time Memory
412070 2021-05-26T13:17:37 Z 송준혁(#7508) Pastiri (COI20_pastiri) C++17
31 / 100
 1000 ms 54492 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 (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 193 ms 48324 KB Output is correct
2 Correct 237 ms 49288 KB Output is correct
3 Correct 238 ms 49228 KB Output is correct
4 Correct 360 ms 54492 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14284 KB Output is correct
2 Correct 10 ms 14308 KB Output is correct
3 Correct 528 ms 32612 KB Output is correct
4 Correct 515 ms 35100 KB Output is correct
5 Correct 572 ms 32260 KB Output is correct
6 Execution timed out 1085 ms 33840 KB Time limit exceeded

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 14160 KB Output is correct
3 Correct 10 ms 14236 KB Output is correct
4 Correct 11 ms 14156 KB Output is correct
5 Correct 10 ms 14156 KB Output is correct
6 Correct 11 ms 14156 KB Output is correct
7 Correct 11 ms 14136 KB Output is correct
8 Correct 10 ms 14156 KB Output is correct
9 Correct 10 ms 14248 KB Output is correct
10 Correct 10 ms 14208 KB Output is correct
11 Correct 11 ms 14156 KB Output is correct
12 Correct 9 ms 14172 KB Output is correct
13 Correct 13 ms 14152 KB Output is correct
14 Correct 10 ms 14156 KB Output is correct
15 Correct 10 ms 14156 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 33436 KB Output is correct
2 Correct 562 ms 40016 KB Output is correct
3 Correct 753 ms 43768 KB Output is correct
4 Correct 654 ms 39372 KB Output is correct
5 Correct 568 ms 38692 KB Output is correct
6 Correct 719 ms 47000 KB Output is correct
7 Correct 773 ms 45516 KB Output is correct
8 Correct 802 ms 44932 KB Output is correct
9 Correct 781 ms 39384 KB Output is correct
10 Correct 583 ms 39136 KB Output is correct
11 Correct 536 ms 41452 KB Output is correct
12 Correct 479 ms 45408 KB Output is correct
13 Correct 534 ms 47212 KB Output is correct
14 Correct 482 ms 42888 KB Output is correct
15 Correct 78 ms 18452 KB Output is correct
16 Execution timed out 1076 ms 37620 KB Time limit exceeded
17 Halted 0 ms 0 KB -