Submission #1166265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166265		MateiKing80	Triumphal arch (POI13_luk)	C++20	100 / 100	945 ms	31204 KiB

luk

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;
vector<int> vec[N];
int dp[N], n;

void dfs(int nod, int papa, int nrE)
{
	int sumfii = 0;
	for (auto i : vec[nod])
		if (i != papa)
			dfs(i, nod, nrE), 
			sumfii += dp[i];
	dp[nod] = max(1, sumfii - nrE + 1);
}

bool doDp(int nrE)
{
	for (int i = 1; i <= n; i ++)
		dp[i] = 0;
	dfs(1, 0, nrE);
	return dp[1] == 1;
}

int main()
{
	cin >> n;
	for (int i = 1; i < n; i ++)
	{
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int pos = -1;
	for (int pas = 1 << 20; pas; pas >>= 1)
		if (!doDp(pos + pas))
			pos += pas;
	cout << pos + 1 << '\n';
}

• 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