Submission #29336

#	Time	Username	Problem	Language	Result	Execution time	Memory
29336		tlwpdus	Untitled (POI11_dyn)	C++11	100 / 100	1833 ms	27340 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

void upd(pii &a, pii b) {
	a.first= min(a.first,b.first);
	a.second=max(a.second,b.second);
}

int n, m;
bool chk[300100];
vector<int> lis[300100];
int L, ans;
pii dfs(int here, int p, int c) {
	//printf("%d, %d, %d\n",here,p,c);
	pii res = pii(c,chk[here]?0:-987654321);
	for (auto &there : lis[here]) {
		if (there==p) continue;
		pii tmp = dfs(there,here,res.first+1);
		tmp.first++; tmp.second++;
		upd(res,tmp);
	}
	if (res.second<=L-res.first) res.second = -987654321;
	if (res.second==L) {
		ans++; //printf("%d!!!!\n",here+1);
		res.first = 0;
		res.second = -987654321;
	}
	//printf("%d : %d, %d\n",here,res.first,res.second);
	return res;
}

int main() {
	int i;

	scanf("%d%d",&n,&m);
	for (i=0;i<n;i++) {
		int a;
		scanf("%d",&a); chk[i] = a;
	}
	for (i=0;i<n-1;i++) {
		int a, b;
		scanf("%d%d",&a,&b); --a; --b;
		lis[a].push_back(b); lis[b].push_back(a);
	}
	int s = 0, e = n;
	while(s<=e) {
		int mid = (s+e)>>1;
		L = mid; ans = 0;
		if (dfs(0,-1,987654321).second>=0) ans++;
		if (ans>m) s = mid+1;
		else e = mid-1;
	}
	printf("%d\n",s);

    return 0;
}

Compilation message (stderr)

dyn.cpp: In function 'int main()':
dyn.cpp:38: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:41:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a); chk[i] = a;
                 ^
dyn.cpp:45:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b); --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