oj.uz

Submission #29345

# Submission time Handle Problem Language Result Execution time Memory
29345 2017-07-19T03:09:57 Z 구사과(#1238) Dynamite (POI11_dyn) C++14
100 / 100
 1816 ms 35048 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], dp[300005], cnt, lim;
int n, m;

int buf[300005];

int dfs(int x, int p){
	for(auto &i : gph[x]){
		if(i == p) continue;
		dfs(i, x);
	}
	int sz = 0;
	for(auto &i : gph[x]){
		if(i == p || dp[i] == -1) continue;
		if(dp[i] + 1 > 2 * lim) cnt++;
		else buf[sz++] = dp[i] + 1;
	}
	sort(buf, buf + sz);
	while(sz >= 2 && buf[sz-1] + buf[sz-2] > 2 * lim) sz--, cnt++;
	if(!sz) return dp[x] = (chk[x] ? 0 : -1);
	return dp[x] = buf[sz-1];
}

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:40: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:42:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&chk[i]);
                      ^
dyn.cpp:51: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 3 ms 12564 KB Output is correct
2 Correct 3 ms 12564 KB Output is correct
3 Correct 3 ms 12564 KB Output is correct
4 Correct 0 ms 12564 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12960 KB Output is correct
2 Correct 39 ms 13356 KB Output is correct
3 Correct 39 ms 13488 KB Output is correct
4 Correct 53 ms 15472 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 14412 KB Output is correct
2 Correct 113 ms 14940 KB Output is correct
3 Correct 289 ms 15072 KB Output is correct
4 Correct 343 ms 16940 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 15996 KB Output is correct
2 Correct 203 ms 16000 KB Output is correct
3 Correct 306 ms 15732 KB Output is correct
4 Correct 433 ms 18624 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 19032 KB Output is correct
2 Correct 849 ms 20496 KB Output is correct
3 Correct 1816 ms 26764 KB Output is correct
4 Correct 1519 ms 26764 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 23960 KB Output is correct
2 Correct 896 ms 22876 KB Output is correct
3 Correct 1076 ms 25788 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1619 ms 32648 KB Output is correct
2 Correct 1516 ms 22880 KB Output is correct
3 Correct 1433 ms 35048 KB Output is correct
4 Correct 636 ms 24020 KB Output is correct