Submission #1990398


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);
		swap(augl, augr);
	}

	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

Submission Time
Task E - Shik and Travel
User semiexp
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 1926 Byte
Status AC
Exec Time 1263 ms
Memory 23424 KB

Compile Error

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

Set Name Sample All
Score / Max Score 0 / 0 1400 / 1400
Status
AC × 4
AC × 54
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt, example3.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, example0.txt, example1.txt, example2.txt, example3.txt
Case Name Status Exec Time Memory
000.txt AC 13 ms 4992 KB
001.txt AC 13 ms 4992 KB
002.txt AC 13 ms 4992 KB
003.txt AC 13 ms 4992 KB
004.txt AC 13 ms 4992 KB
005.txt AC 14 ms 4992 KB
006.txt AC 13 ms 4992 KB
007.txt AC 13 ms 4992 KB
008.txt AC 13 ms 4992 KB
009.txt AC 13 ms 4992 KB
010.txt AC 715 ms 8064 KB
011.txt AC 717 ms 8064 KB
012.txt AC 720 ms 10112 KB
013.txt AC 751 ms 8064 KB
014.txt AC 726 ms 8064 KB
015.txt AC 709 ms 8064 KB
016.txt AC 719 ms 8064 KB
017.txt AC 713 ms 8064 KB
018.txt AC 708 ms 8064 KB
019.txt AC 687 ms 8064 KB
020.txt AC 749 ms 8064 KB
021.txt AC 710 ms 8064 KB
022.txt AC 730 ms 8064 KB
023.txt AC 700 ms 8064 KB
024.txt AC 735 ms 8064 KB
025.txt AC 748 ms 8064 KB
026.txt AC 643 ms 8064 KB
027.txt AC 728 ms 8192 KB
028.txt AC 642 ms 8064 KB
029.txt AC 656 ms 8064 KB
030.txt AC 669 ms 8064 KB
031.txt AC 772 ms 8192 KB
032.txt AC 730 ms 8064 KB
033.txt AC 667 ms 8064 KB
034.txt AC 662 ms 8064 KB
035.txt AC 738 ms 8064 KB
036.txt AC 664 ms 8064 KB
037.txt AC 648 ms 8064 KB
038.txt AC 666 ms 8064 KB
039.txt AC 518 ms 8064 KB
040.txt AC 1172 ms 13156 KB
041.txt AC 1260 ms 12912 KB
042.txt AC 1245 ms 13264 KB
043.txt AC 1263 ms 12928 KB
044.txt AC 425 ms 23424 KB
045.txt AC 595 ms 15744 KB
046.txt AC 701 ms 17920 KB
047.txt AC 596 ms 16384 KB
048.txt AC 601 ms 20992 KB
049.txt AC 3 ms 4992 KB
example0.txt AC 3 ms 4992 KB
example1.txt AC 3 ms 4992 KB
example2.txt AC 3 ms 4992 KB
example3.txt AC 3 ms 4992 KB