oj.uz

Submission #29307

# Submission time Handle Problem Language Result Execution time Memory
29307 2017-07-19T02:00:34 Z khsoo01 Dynamite (POI11_dyn) C++11
100 / 100
 2173 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 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 Correct 3 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 0 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 33 ms 13356 KB Output is correct
3 Correct 33 ms 13488 KB Output is correct
4 Correct 59 ms 14404 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 14412 KB Output is correct
2 Correct 113 ms 14940 KB Output is correct
3 Correct 316 ms 15072 KB Output is correct
4 Correct 223 ms 16752 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 15996 KB Output is correct
2 Correct 259 ms 16000 KB Output is correct
3 Correct 486 ms 15732 KB Output is correct
4 Correct 263 ms 18784 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 19032 KB Output is correct
2 Correct 1026 ms 20496 KB Output is correct
3 Correct 1539 ms 24688 KB Output is correct
4 Correct 1349 ms 24688 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1979 ms 23452 KB Output is correct
2 Correct 1629 ms 22876 KB Output is correct
3 Correct 2173 ms 25216 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1846 ms 27160 KB Output is correct
2 Correct 1129 ms 22880 KB Output is correct
3 Correct 1896 ms 28372 KB Output is correct
4 Correct 706 ms 24020 KB Output is correct