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 |
|
|
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 |