oj.uz

Submission #29335

# Submission time Handle Problem Language Result Execution time Memory
29335 2017-07-19T02:52:18 Z 시제연(#1167) Dynamite (POI11_dyn) C++11
100 / 100
 1759 ms 27336 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

void upd(pii &a, pii b) {
	a.first= min(a.first,b.first);
	a.second=max(a.second,b.second);
}

int n, m;
bool chk[300100];
vector<int> lis[300100];
int L, ans;
pii dfs(int here, int p, int c) {
	//printf("%d, %d, %d\n",here,p,c);
	pii res = pii(c,chk[here]?0:-987654321);
	for (auto &there : lis[here]) {
		if (there==p) continue;
		pii tmp = dfs(there,here,res.first+1);
		tmp.first++; tmp.second++;
		upd(res,tmp);
	}
	if (res.second<=L-res.first) res.second = -987654321;
	if (res.second==L) {
		ans++; //printf("%d!!!!\n",here+1);
		res.first = 0;
		res.second = -987654321;
	}
	//printf("%d : %d, %d\n",here,res.first,res.second);
	return res;
}

int main() {
	int i;

	scanf("%d%d",&n,&m);
	for (i=0;i<n;i++) {
		int a;
		scanf("%d",&a); chk[i] = a;
	}
	for (i=0;i<n-1;i++) {
		int a, b;
		scanf("%d%d",&a,&b); --a; --b;
		lis[a].push_back(b); lis[b].push_back(a);
	}
	int s = 0, e = n;
	while(s<=e) {
		int mid = (s+e)>>1;
		L = mid; ans = 0;
		if (dfs(0,-1,987654321).second>=0) ans++;
		if (ans>m) s = mid+1;
		else e = mid-1;
	}
	printf("%d\n",s);

    return 0;
}

Compilation message

dyn.cpp: In function 'int main()':
dyn.cpp:38:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
dyn.cpp:41:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a); chk[i] = a;
                 ^
dyn.cpp:45:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b); --a; --b;
                      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9740 KB Output is correct
2 Correct 39 ms 10136 KB Output is correct
3 Correct 39 ms 10268 KB Output is correct
4 Correct 56 ms 11528 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11192 KB Output is correct
2 Correct 119 ms 11720 KB Output is correct
3 Correct 259 ms 11852 KB Output is correct
4 Correct 253 ms 14136 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 12776 KB Output is correct
2 Correct 289 ms 12780 KB Output is correct
3 Correct 363 ms 12512 KB Output is correct
4 Correct 486 ms 16492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 15812 KB Output is correct
2 Correct 1012 ms 17276 KB Output is correct
3 Correct 853 ms 22956 KB Output is correct
4 Correct 1506 ms 22956 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1759 ms 20728 KB Output is correct
2 Correct 649 ms 19656 KB Output is correct
3 Correct 963 ms 23048 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 913 ms 25720 KB Output is correct
2 Correct 619 ms 19660 KB Output is correct
3 Correct 1493 ms 27336 KB Output is correct
4 Correct 403 ms 20800 KB Output is correct