Submission #28941

#	Time	Username	Problem	Language	Result	Execution time	Memory
28941		khsoo01	Triumphal arch (POI13_luk)	C++11	100 / 100	1193 ms	23796 KiB

luk

#include<bits/stdc++.h>
using namespace std;
const int N = 300005;

int n, v[N], cur;
vector<int> adj[N];

void solve (int C, int P) {
	v[C] = cur - (int)adj[C].size() + !!P;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		solve(T, C);
		if(v[T] < 0) v[C] += v[T];
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	int S = 0, E = n;
	while(S < E) {
		int M = (S+E)/2;
		cur = M; solve(1, 0);
		v[1] < 0 ? S = M+1 : E = M;
	}
	printf("%d\n",S);
}

Compilation message (stderr)

luk.cpp: In function 'int main()':
luk.cpp:19:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
luk.cpp:22:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
                      ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10