Submission #1696703


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N = 150000;
typedef pair<int, int> pii;
typedef long long ll;
vector<pii>f[N], t1, t2;
int n, L[N], R[N];
ll l, r, mid, dep[N];

struct Edge {
	int to, w;
	Edge *next;
	Edge () {}
	Edge (int to, int w, Edge *next) : to(to), w(w), next(next) {}
}*head[N], pool[N << 1], *pis = pool;

bool cmp2 (const pii &A, const pii &B) { return dep[A.first] < dep[B.first]; }
bool cmp (const pii &A, const pii &B) { return dep[A.second] < dep[B.second]; }

void Dfs (int u, int fa) {
	for (Edge *now = head[u]; now; now = now -> next) if (now -> to != fa) {
		if (!L[u]) L[u] = now -> to;
		else R[u] = now -> to;
	}
	for (Edge *now = head[u]; now; now = now -> next) if (now -> to != fa) dep[now -> to] = dep[u] + now -> w, Dfs(now -> to, u);
	if (!L[u]) return f[u].push_back(pii(u, u));
	vector<pii>&tl = f[L[u]], &tr = f[R[u]], &tx = f[u];
	int lenl = tl.size(), lenr = tr.size();
	sort(tr.begin(), tr.end(), cmp2);
	sort(tl.begin(), tl.end(), cmp);
	t1.clear(); t2.clear();
	int now = -1;
	for (int i = lenl - 1, j = 0; ~i; --i) {
		for (; j < lenr && dep[tl[i].second] + dep[tr[j].first] - dep[u] * 2 <= mid; ++j) {
			if (now == -1 || dep[tr[j].second] < dep[now]) now = tr[j].second;
		}
		if (now != -1) t1.push_back(pii(tl[i].first, now));
	}
	sort(tl.begin(), tl.end(), cmp2);
	sort(tr.begin(), tr.end(), cmp);
	now = -1;
	for (int i = lenr - 1, j = 0; ~i; --i) {
		for (; j < lenl && dep[tl[j].first] + dep[tr[i].second] - dep[u] * 2 <= mid; ++j) {
			if (now == -1 || dep[tl[j].second] < dep[now]) now = tl[j].second;
		}
		if (now != -1) t2.push_back(pii(tr[i].first, now));
	}
	if (t1.size() > t2.size()) {
		swap(t1, tx);
		for (int i = t2.size() - 1; ~i; --i) tx.push_back(t2[i]);
	} else {
		swap(t2, tx);
		for (int i = t1.size() - 1; ~i; --i) tx.push_back(t1[i]);
	}
}

bool Judge () {
	Dfs(1, 0);
	return f[1].size();
}

int main () {
	scanf("%d", &n);
	for (int i = 2, j, k; i <= n; ++i) {
		scanf("%d%d", &j, &k);
		head[i] = new (pis++) Edge(j, k, head[i]);
		head[j] = new (pis++) Edge(i, k, head[j]);
	}
	l = 0, r = 2e10;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (Judge()) r = mid - 1;
		else l = mid + 1;
	}
	printf("%lld\n", l);
	return 0;
}

Submission Info

Submission Time
Task E - Shik and Travel
User DraZxlNDdt
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2290 Byte
Status TLE
Exec Time 5284 ms
Memory 481680 KB

Compile Error

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 4
AC × 15
TLE × 39
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 488 ms 29436 KB
001.txt AC 568 ms 36220 KB
002.txt AC 501 ms 36860 KB
003.txt AC 495 ms 35644 KB
004.txt AC 538 ms 37372 KB
005.txt AC 559 ms 35644 KB
006.txt AC 496 ms 35192 KB
007.txt AC 462 ms 33660 KB
008.txt AC 540 ms 37388 KB
009.txt AC 438 ms 30208 KB
010.txt TLE 5280 ms 380248 KB
011.txt TLE 5281 ms 363352 KB
012.txt TLE 5277 ms 363880 KB
013.txt TLE 5278 ms 394600 KB
014.txt TLE 5278 ms 377128 KB
015.txt TLE 5278 ms 382736 KB
016.txt TLE 5278 ms 377532 KB
017.txt TLE 5277 ms 368528 KB
018.txt TLE 5278 ms 380128 KB
019.txt TLE 5279 ms 397028 KB
020.txt TLE 5277 ms 370392 KB
021.txt TLE 5280 ms 405100 KB
022.txt TLE 5278 ms 386480 KB
023.txt TLE 5278 ms 388908 KB
024.txt TLE 5278 ms 379488 KB
025.txt TLE 5279 ms 390652 KB
026.txt TLE 5282 ms 451688 KB
027.txt TLE 5277 ms 382224 KB
028.txt TLE 5284 ms 481680 KB
029.txt TLE 5281 ms 442496 KB
030.txt TLE 5274 ms 330436 KB
031.txt TLE 5276 ms 325060 KB
032.txt TLE 5274 ms 325188 KB
033.txt TLE 5274 ms 325828 KB
034.txt TLE 5274 ms 333380 KB
035.txt TLE 5277 ms 340032 KB
036.txt TLE 5276 ms 349760 KB
037.txt TLE 5277 ms 386752 KB
038.txt TLE 5280 ms 342208 KB
039.txt TLE 5281 ms 440256 KB
040.txt TLE 5274 ms 332612 KB
041.txt TLE 5273 ms 317636 KB
042.txt TLE 5279 ms 318276 KB
043.txt TLE 5274 ms 318916 KB
044.txt TLE 5279 ms 371324 KB
045.txt TLE 5278 ms 366760 KB
046.txt TLE 5279 ms 367616 KB
047.txt TLE 5284 ms 366836 KB
048.txt TLE 5278 ms 363228 KB
049.txt AC 4 ms 7936 KB
example0.txt AC 4 ms 7936 KB
example1.txt AC 4 ms 7936 KB
example2.txt AC 4 ms 7936 KB
example3.txt AC 3 ms 7936 KB