oj.uz

Submission #29341

# Submission time Handle Problem Language Result Execution time Memory
29341 2017-07-19T03:01:49 Z 구사과(#1238) Dynamite (POI11_dyn) C++14
100 / 100
 2486 ms 33124 KB 
#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 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);
                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10228 KB Output is correct
2 Correct 3 ms 10228 KB Output is correct
3 Correct 0 ms 10228 KB Output is correct
4 Correct 0 ms 10228 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10228 KB Output is correct
2 Correct 0 ms 10228 KB Output is correct
3 Correct 3 ms 10228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10228 KB Output is correct
2 Correct 0 ms 10228 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10228 KB Output is correct
2 Correct 3 ms 10228 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10624 KB Output is correct
2 Correct 46 ms 11020 KB Output is correct
3 Correct 46 ms 11152 KB Output is correct
4 Correct 56 ms 12948 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 12076 KB Output is correct
2 Correct 153 ms 12604 KB Output is correct
3 Correct 196 ms 12736 KB Output is correct
4 Correct 409 ms 16360 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 13660 KB Output is correct
2 Correct 373 ms 13664 KB Output is correct
3 Correct 526 ms 13396 KB Output is correct
4 Correct 746 ms 19512 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 16696 KB Output is correct
2 Correct 993 ms 18160 KB Output is correct
3 Correct 2069 ms 27612 KB Output is correct
4 Correct 1983 ms 27608 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2159 ms 22732 KB Output is correct
2 Correct 1593 ms 20540 KB Output is correct
3 Correct 2449 ms 23388 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2486 ms 31760 KB Output is correct
2 Correct 1586 ms 20544 KB Output is correct
3 Correct 2439 ms 33124 KB Output is correct
4 Correct 796 ms 25832 KB Output is correct