oj.uz

Submission #29343

# Submission time Handle Problem Language Result Execution time Memory
29343 2017-07-19T03:04:46 Z 구사과(#1238) Dynamite (POI11_dyn) C++11
100 / 100
 2329 ms 35880 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 r = -1;

int trial(int l){
	cnt = 1;
	lim = l;
	dfs(r, -1);
	return cnt;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++){
		scanf("%d",&chk[i]);
		if(chk[i]) r = i;
	}
	if(r == -1){
		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/2;
	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:38: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:40:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&chk[i]);
                      ^
dyn.cpp:49: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 0 ms 10228 KB Output is correct
3 Correct 3 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 3 ms 10228 KB Output is correct
2 Correct 0 ms 10228 KB Output is correct
3 Correct 0 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 0 ms 10228 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10624 KB Output is correct
2 Correct 46 ms 11020 KB Output is correct
3 Correct 39 ms 11152 KB Output is correct
4 Correct 69 ms 13556 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12076 KB Output is correct
2 Correct 173 ms 12736 KB Output is correct
3 Correct 356 ms 12736 KB Output is correct
4 Correct 369 ms 15136 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 13660 KB Output is correct
2 Correct 273 ms 13664 KB Output is correct
3 Correct 396 ms 13396 KB Output is correct
4 Correct 543 ms 16956 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 966 ms 16704 KB Output is correct
2 Correct 1069 ms 18160 KB Output is correct
3 Correct 1706 ms 26528 KB Output is correct
4 Correct 1146 ms 26528 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1519 ms 22164 KB Output is correct
2 Correct 1446 ms 20540 KB Output is correct
3 Correct 2206 ms 24328 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2233 ms 34324 KB Output is correct
2 Correct 1466 ms 20544 KB Output is correct
3 Correct 2329 ms 35880 KB Output is correct
4 Correct 459 ms 25832 KB Output is correct