oj.uz

Submission #29339

# Submission time Handle Problem Language Result Execution time Memory
29339 2017-07-19T02:55:16 Z 구사과(#1238) Dynamite (POI11_dyn) C++14
90 / 100
 2503 ms 33116 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;
	dfs(1, 0);
	return cnt;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++) scanf("%d",&chk[i]);
	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:37: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:38: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:41: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 10224 KB Output is correct
2 Correct 3 ms 10224 KB Output is correct
3 Correct 3 ms 10224 KB Output is correct
4 Correct 3 ms 10224 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 10224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10620 KB Output is correct
2 Correct 49 ms 11016 KB Output is correct
3 Correct 53 ms 11148 KB Output is correct
4 Correct 96 ms 13108 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 12072 KB Output is correct
2 Correct 209 ms 12600 KB Output is correct
3 Correct 369 ms 12732 KB Output is correct
4 Correct 439 ms 16356 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 13656 KB Output is correct
2 Correct 466 ms 13660 KB Output is correct
3 Correct 573 ms 13392 KB Output is correct
4 Correct 753 ms 19504 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1376 ms 16692 KB Output is correct
2 Correct 1273 ms 18156 KB Output is correct
3 Correct 2126 ms 27604 KB Output is correct
4 Correct 1929 ms 27608 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2346 ms 22752 KB Output is correct
2 Correct 1526 ms 20536 KB Output is correct
3 Correct 2503 ms 26284 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2393 ms 31760 KB Output is correct
2 Correct 1643 ms 20540 KB Output is correct
3 Correct 2386 ms 33116 KB Output is correct
4 Correct 739 ms 25828 KB Output is correct