oj.uz

Submission #29306

# Submission time Handle Problem Language Result Execution time Memory
29306 2017-07-19T02:00:00 Z 김현수(#1165) Dynamite (POI11_dyn) C++14
100 / 100
 2233 ms 28372 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 300005, inf = 1e9;

int n, m, cur, a[N], dt[N], lft[N], tnt;

vector<int> adj[N];

void solve (int C, int P) {
	dt[C] = (a[C] ? 0 : -inf);
	lft[C] = -inf;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		solve(T, C);
		dt[C] = max(dt[C], dt[T] + 1);
		lft[C] = max(lft[C], lft[T] - 1);
	}
	if(dt[C] <= lft[C]) dt[C] = -inf;
	if(dt[C] >= cur) {tnt++; dt[C] = -inf; lft[C] = cur;}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	for(int i=1;i<n;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	int S = 0, E = n;
	while(S < E) {
		cur = (S+E)/2; tnt = 0;
		solve(1, 0);
		if(dt[1] >= 0) tnt++;
		tnt <= m ? E = cur : S = cur+1;
	}
	printf("%d\n", S);
}

Compilation message

dyn.cpp: In function 'int main()':
dyn.cpp:25:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
dyn.cpp:27:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
dyn.cpp:31:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12564 KB Output is correct
2 Correct 0 ms 12564 KB Output is correct
3 Correct 0 ms 12564 KB Output is correct
4 Correct 0 ms 12564 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12564 KB Output is correct
2 Correct 3 ms 12564 KB Output is correct
3 Correct 3 ms 12564 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12564 KB Output is correct
2 Correct 0 ms 12564 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12564 KB Output is correct
2 Correct 0 ms 12564 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12960 KB Output is correct
2 Correct 56 ms 13356 KB Output is correct
3 Correct 46 ms 13488 KB Output is correct
4 Correct 73 ms 14404 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 14412 KB Output is correct
2 Correct 106 ms 14940 KB Output is correct
3 Correct 233 ms 15072 KB Output is correct
4 Correct 279 ms 16752 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 15996 KB Output is correct
2 Correct 316 ms 16000 KB Output is correct
3 Correct 499 ms 15732 KB Output is correct
4 Correct 509 ms 18788 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 979 ms 19032 KB Output is correct
2 Correct 1139 ms 20496 KB Output is correct
3 Correct 1629 ms 24692 KB Output is correct
4 Correct 1443 ms 24688 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1966 ms 23452 KB Output is correct
2 Correct 1546 ms 22876 KB Output is correct
3 Correct 2233 ms 25216 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1713 ms 27164 KB Output is correct
2 Correct 1563 ms 22880 KB Output is correct
3 Correct 2229 ms 28372 KB Output is correct
4 Correct 523 ms 24020 KB Output is correct