Submission #29307

#	Time	Username	Problem	Language	Result	Execution time	Memory
29307		khsoo01	Untitled (POI11_dyn)	C++11	100 / 100	2173 ms	28372 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10