oj.uz

Submission #28973

# Submission time Handle Problem Language Result Execution time Memory
28973 2017-07-18T02:31:48 Z tlwpdus Triumphal arch (POI13_luk) C++11
100 / 100
 1339 ms 25192 KB 
#include <bits/stdc++.h>

using namespace std;

int n, t;
vector<int> lis[300100];
int d[300100];

void dfs(int here, int p) {
	int i, sum = 0;
	for (auto &there : lis[here]) {
		if (there==p) continue;
		dfs(there,here);
		sum += d[there];
	}
	d[here] = max(sum-t+1,1);
}

int main() {
	int i;

	scanf("%d",&n);
	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 m = (s+e)>>1;
		t = m;
		dfs(0,-1);
		if (d[0]>1) s = m+1;
		else e = m-1;
	}
	printf("%d\n",s);

    return 0;
}

Compilation message

luk.cpp: In function 'void dfs(int, int)':
luk.cpp:10:6: warning: unused variable 'i' [-Wunused-variable]
  int i, sum = 0;
      ^
luk.cpp: In function 'int main()':
luk.cpp:22:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
luk.cpp:25: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 0 ms 10224 KB Output is correct
2 Correct 0 ms 10224 KB Output is correct
3 Correct 0 ms 10224 KB Output is correct

Subtask #2
10.0 / 10.0

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

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
3 Correct 0 ms 10224 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10620 KB Output is correct
2 Correct 9 ms 10720 KB Output is correct
3 Correct 9 ms 10620 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 11280 KB Output is correct
2 Correct 29 ms 11948 KB Output is correct
3 Correct 13 ms 11412 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 13524 KB Output is correct
2 Correct 229 ms 15260 KB Output is correct
3 Correct 63 ms 13924 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 16824 KB Output is correct
2 Correct 766 ms 21284 KB Output is correct
3 Correct 223 ms 17632 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1339 ms 20124 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1326 ms 20124 KB Output is correct
2 Correct 1299 ms 25192 KB Output is correct
3 Correct 473 ms 21160 KB Output is correct