oj.uz

Submission #29336

# Submission time Handle Problem Language Result Execution time Memory
29336 2017-07-19T02:52:52 Z tlwpdus Dynamite (POI11_dyn) C++11
100 / 100
 1833 ms 27340 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 0 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 3 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 3 ms 9344 KB Output is correct

Subtask #4
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 #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9740 KB Output is correct
2 Correct 29 ms 10136 KB Output is correct
3 Correct 36 ms 10268 KB Output is correct
4 Correct 53 ms 11528 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 11192 KB Output is correct
2 Correct 106 ms 11720 KB Output is correct
3 Correct 303 ms 11852 KB Output is correct
4 Correct 206 ms 14132 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 12776 KB Output is correct
2 Correct 203 ms 12780 KB Output is correct
3 Correct 359 ms 12512 KB Output is correct
4 Correct 406 ms 16492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 776 ms 15812 KB Output is correct
2 Correct 946 ms 17276 KB Output is correct
3 Correct 1076 ms 22964 KB Output is correct
4 Correct 666 ms 22956 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1126 ms 20736 KB Output is correct
2 Correct 1253 ms 19656 KB Output is correct
3 Correct 1833 ms 23044 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1669 ms 25728 KB Output is correct
2 Correct 1319 ms 19660 KB Output is correct
3 Correct 1783 ms 27340 KB Output is correct
4 Correct 283 ms 20800 KB Output is correct