oj.uz

Submission #29300

# Submission time Handle Problem Language Result Execution time Memory
29300 2017-07-19T01:51:08 Z 김현수(#1165) Dynamite (POI11_dyn) C++14
30 / 100
 2063 ms 27164 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);
		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
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
3 Correct 0 ms 12564 KB Output is correct
4 Incorrect 0 ms 12564 KB Output isn't correct

Subtask #2
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
3 Correct 0 ms 12564 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
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 #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14412 KB Output is correct
2 Correct 113 ms 14940 KB Output is correct
3 Correct 289 ms 15072 KB Output is correct
4 Incorrect 199 ms 16752 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 15996 KB Output is correct
2 Correct 279 ms 16000 KB Output is correct
3 Correct 473 ms 15732 KB Output is correct
4 Incorrect 516 ms 18784 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 19032 KB Output is correct
2 Correct 1056 ms 20496 KB Output is correct
3 Incorrect 1616 ms 24688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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