Submission #1611277

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define iter(i, n) forw(i, 1, n)
#define forw(i, a, b) for (int i = a; i <= b; ++i)

typedef long long i64;
#define NR 201000

typedef pair<i64, i64> pii;
#define fi first
#define se second
int n, lc[NR], rc[NR], fw[NR];
vector<pii> vec[NR];
i64 lim;

void dfs(int x) {
//	printf("d %d %d %d\n", x, lc[x], rc[x]);
	if (lc[x] == 0) {
		vec[x].push_back(pii(0, 0));
		return;
	}

	int i = lc[x], j = rc[x];
	dfs(i);
	dfs(j);

	if (vec[i].size() > vec[j].size()) swap(i, j);

	vector<pii> tmp; vec[x].clear();

	for (pii p : vec[i]) {
		int index = lower_bound(vec[j].begin(), vec[j].end(), pii(lim - p.se - fw[i] - fw[j] + 1, 0)) - vec[j].begin();

	//		printf("!!%lld %lld %d\n", lim, lim - p.se - fw[i] - fw[j] + 1, index);
		if (index > 0) {
			--index;
			tmp.push_back(pii(p.fi + fw[i], vec[j][index].se + fw[j]));
			tmp.push_back(pii(vec[j][index].se + fw[j], p.fi + fw[i]));
		}
	}

	sort(tmp.begin(), tmp.end());
	i64 lst = 1e12;
	for (pii p : tmp) if (p.se < lst) vec[x].push_back(p), lst = p.se;
}

bool check(i64 l) {
	lim = l;
	dfs(1);
	return !vec[1].empty();	
}

int main() {
	scanf("%d", &n);
	forw(i, 2, n) {
		int fa;
		scanf("%d%d", &fa, &fw[i]);
		if (lc[fa]) rc[fa] = i;
		else lc[fa] = i;
	}

	i64 l = 0, r = 1e11;
	for (; l < r;) {
		i64 mid = (l + r) / 2;

		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	printf("%lld\n", l);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:57:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:60:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &fa, &fw[i]);
                             ^

Judge Result