Submission #1884018

---

Source Code Expand

// Shik and Travel
// * frank_c1
// * 2017 / 12 / 18
 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int maxn = (int)(1e5) + 5;
int wi[maxn], ai[maxn], bi[maxn];
int st[maxn], su[maxn];
pii ci[maxn * 22], ta[maxn], tb[maxn];
int n, idx;

bool chk(int x) {
	idx = 0;
	for (int i = n; i >= 1; --i) {
		st[i] = idx + 1;
		if (!ai[i]) ci[++idx] = make_pair(0, 0);
		else {
			int u = ai[i], v = bi[i];
			if (su[u] > su[v]) swap(u, v);
			int mx = x - wi[u] - wi[v];
			int ca = 0, cb = 0, ww = (int)(1e9), ps = 1;
			for (int j = st[u]; j < st[u] + su[u]; ++j) ta[++ca] = make_pair(ci[j].first, ci[j].second);
			for (int j = st[v]; j < st[v] + su[v]; ++j) tb[++cb] = make_pair(ci[j].second, ci[j].first);
			sort(ta + 1, ta + ca + 1); sort(tb + 1, tb + cb + 1);
			for (int j = ca; j >= 1; --j) {
				while (ps <= cb && ta[j].first + tb[ps].first <= mx) ww = min(ww, tb[ps++].second);	
				if (ps > 1) ci[++idx] = make_pair(ww + wi[v], ta[j].second + wi[u]);
			}
			ca = cb = 0; ww = (int)(1e9); ps = 1;
			for (int j = st[u]; j < st[u] + su[u]; ++j) ta[++ca] = make_pair(ci[j].second, ci[j].first);
			for (int j = st[v]; j < st[v] + su[v]; ++j) tb[++cb] = make_pair(ci[j].first, ci[j].second);
			sort(ta + 1, ta + ca + 1); sort(tb + 1, tb + cb + 1);
			for (int j = ca; j >= 1; --j) {
				while (ps <= cb && ta[j].first + tb[ps].first <= mx) ww = min(ww, tb[ps++].second);
				if (ps > 1) ci[++idx] = make_pair(ta[j].second + wi[u], ww + wi[v]);
			}
		}
		su[i] = idx - st[i] + 1;
	}
	return su[1] > 0;
}

int main() {
	scanf("%d", &n);
	for (int i = 2; i <= n; ++i) {
		int f; scanf("%d%d", &f, &wi[i]);
		if (!ai[f]) ai[f] = i; else bi[f] = i;
	}
	int l = 0, r = 20 * (1 << 17);
	while (l < r) {
		int mid = (l + r) >> 1;
		if (chk(mid)) r = mid; else l = mid + 1;
	}
	return printf("%d\n", l), 0;
}

Submission Info

Compile Error

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

Judge Result