Submission #1990391

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N;
vector<pair<i64, i64> > ch[202020];

vector<pair<i64, i64> > canonize(vector<pair<i64, i64> > &seq)
{
	sort(seq.begin(), seq.end());
	vector<pair<i64, i64> > ret;

	i64 upp = 1LL << 50LL;
	for (auto e : seq) {
		if (e.second < upp) {
			ret.push_back(e);
			upp = e.second;
		}
	}

	return ret;
}

vector<pair<i64, i64> > solve(int p, i64 thr)
{
	if (ch[p].size() == 0) {
		return{ {0LL, 0LL} };
	}

	vector<pair<i64, i64> > left = solve(ch[p][0].first, thr);
	int augl = ch[p][0].second;
	vector<pair<i64, i64> > right = solve(ch[p][1].first, thr);
	int augr = ch[p][1].second;

	if (left.size() > right.size()) swap(left, right);

	vector<pair<i64, i64> > ret;
	for (int i = 0; i < left.size(); ++i) {
		i64 inl = left[i].first + augl, outl = left[i].second + augl;
		int idx = lower_bound(right.begin(), right.end(), make_pair(thr - augr - outl, 1LL << 50LL)) - right.begin() - 1;
		if (idx < 0) continue;
		i64 outr = right[idx].second + augr;

		ret.push_back({ inl, outr });
		ret.push_back({ outr, inl });
	}

	return canonize(ret);
}

bool isok(i64 thr)
{
	return solve(0, thr).size() > 0;
}

int main()
{
	scanf("%d", &N);
	for (int i = 1; i < N; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a;
		ch[a].push_back({ i, b });
	}

	i64 left = 0, right = 1LL << 40LL;
	while (left < right) {
		i64 mid = (left + right) / 2;
		if (isok(mid)) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	printf("%lld\n", left);
	return 0;
}

Submission Info

Compile Error

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

Judge Result