Submission #1697866

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
const int xn = 131073;
std::vector < std::pair < int, int > > V[xn];
int N, q[xn];
std::vector < std::pair < long long, long long > > ans[xn];
void merge(auto &O, const auto &V0, const auto &V1, long long E0, long long E1, long long LIM)
{
	O.clear();
	std::vector < std::pair < long long, long long > > TMP;
	for (auto &i : V0)
	{
		auto it = std::upper_bound(V1.begin(), V1.end(), std::make_pair(LIM - E0 - E1 - i.second, 1LL << 60));
		if (it != V1.begin())
		{
			std::pair < long long, long long > To_Push_back = { i.first + E0, (it - 1) -> second + E1 };
			TMP.push_back(To_Push_back);
			std::swap(To_Push_back.first, To_Push_back.second);
			TMP.push_back(To_Push_back);
		}
	}
	std::sort(TMP.begin(), TMP.end());
	for (auto i : TMP)
		if (O.empty() || i.second < O.back().second)
			O.push_back(i);
}
bool check(long long mid)
{
	for (int i = N; i; i--)
	{
		int u = q[i];
		if (V[u].empty())
			ans[u] = { { 0, 0 } };
		else
			merge(ans[u], ans[V[u][0].first], ans[V[u][1].first], V[u][0].second, V[u][1].second, mid);
		if (ans[u].empty())
			return false;
	}
	return true;
}
int main()
{
	scanf("%d", &N);
	for (int i = 2, f, l; i <= N; i++)
	{
		scanf("%d%d", &f, &l);
		V[f].push_back({ i, l });
	}
	int H = 0, T = 1;
	q[1] = 1;
	while (H < T)
	{
		int u = q[++H];
		for (auto v : V[u])
			q[++T] = v.first;
	}
	long long l = 0, r = 1LL << 40;
	while (l < r)
	{
		long long m = l + r >> 1;
		if (check(m))
			r = m;
		else
			l = m + 1;
	}
	printf("%lld\n", l);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:44:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:47:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &f, &l);
                        ^

Judge Result