Submission #1990349

---

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<int, int> > ch[202020];

void augment(vector<pair<int, int> > &ls, int a)
{
	for (auto &e : ls) {
		e.first += a;
		e.second += a;
	}
}
vector<pair<int, int> > canonize(vector<pair<int, int> > &seq)
{
	sort(seq.begin(), seq.end());
	vector<pair<int, int> > ret;

	int upp = 1001001001;
	for (auto e : seq) {
		if (e.second < upp) {
			ret.push_back(e);
			upp = e.second;
		}
	}

	return ret;
}

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

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

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

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

	return canonize(ret);
}

bool isok(int 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 = 1000000007;
	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:75:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:78: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