Submission #29340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
29340	2017-07-19T03:01:42 Z	구사과(#1238)	Dynamite (POI11_dyn)	C++	Compilation error	0 ms	0 KB

dyn

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

vector<int> gph[300005];
int chk[300005], cnt, lim;
int n, m;

int dfs(int x, int p){
	vector<int> v;
	for(auto &i : gph[x]){
		if(i == p) continue;
		int w = dfs(i, x);
		if(w != -1) v.push_back(w + 1);
	}
	sort(v.begin(), v.end());
	while(v.size() >= 2 && v.back() + v[v.size() - 2] > 2 * lim){
		v.pop_back();
		cnt++;
	}
	while(v.size() && v.back() > 2 * lim) v.pop_back(), cnt++;
	if(v.empty()) return chk[x] ? 0 : -1;
	return v.back();
}


int trial(int l){
	cnt = 1;
	lim = l;
	for(int i=1; i<=n; i++){
		if(chk[i]){
			dfs(i, -1);
			break;
		}
	}
	return cnt;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++) scanf("%d",&chk[i]);
	if(*max_element(chk, chk + n + 1) == 0){
		puts("0");
		return 0;
	}
	for(int i=1; i<n; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	int s = 0, e = n;
	while(s != e){
		int mi = (s+e)/2;
		if(trial(mi) <= m) e = mi;
		else s = mi+1;
	}
	cout << s;
}

Compilation message

dyn.cpp: In function 'int dfs(int, int)':
dyn.cpp:13:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : gph[x]){
      ^
dyn.cpp:13:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : gph[x]){
            ^
dyn.cpp:13:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : gph[x]){
                ^
dyn.cpp: In function 'int main()':
dyn.cpp:42:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
dyn.cpp:43:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d",&chk[i]);
                                             ^
dyn.cpp:50:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s,&e);
                       ^