Submission #1453838
Source Code Expand
#include <cstdio>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
int main() {
int n; scanf("%d", &n);
vector<vector<pair<int, int> > > g(n);
repeat (i, n - 1) {
int a, v; scanf("%d%d", &a, &v);
g[a - 1].emplace_back(i + 1, v);
g[i + 1].emplace_back(a - 1, v);
}
function<vector<tuple<ll, ll, ll> > (int, int)> dfs = [&](int i, int parent) {
vector<tuple<ll, ll, ll> > left;
vector<tuple<ll, ll, ll> > right;
for (auto edge : g[i]) {
int j, value; tie(j, value) = edge;
if (j != parent) {
auto x = dfs(j, i);
auto & y = left.empty() ? left : right;
assert (y.empty());
y = move(x);
repeat (i, y.size()) {
get<0>(y[i]) += value;
get<1>(y[i]) += value;
}
}
}
if (left.empty()) {
vector<tuple<ll, ll, ll> > result;
result.emplace_back(0, 0, 0);
return result;
}
assert (not right.empty());
vector<tuple<ll, ll, ll> > result;
if (left.size() < right.size()) {
left.swap(right);
}
for (auto l : left) {
ll l1, l2, lmin; tie(l1, l2, lmin) = l;
for (auto r : right) {
ll r1, r2, rmin; tie(r1, r2, rmin) = r;
auto push = [&](ll a, ll b, ll c) {
if (a < b) swap(a, b);
result.emplace_back(a, b, max(c, max(lmin, rmin)));
};
push(l1, r1, l2 + r2);
push(l1, r2, l2 + r1);
push(l2, r1, l1 + r2);
push(l2, r2, l1 + r1);
}
}
int k = result.size();
for (int i = 0; i < k; ++ i) {
ll i1, i2, imin; tie(i1, i2, imin) = result[i];
bool found = false;
repeat (j, k) if (j != i) {
ll j1, j2, jmin; tie(j1, j2, jmin) = result[j];
if (j1 <= i1 and j2 <= i2 and jmin <= imin) {
found = true;
break;
}
}
if (found) {
swap(result[i], result[k - 1]);
-- i;
-- k;
}
}
result.resize(k);
if (result.size() >= 1000) {
whole(random_shuffle, result);
result.resize(1000);
}
return result;
};
auto acc = dfs(0, -1);
constexpr ll inf = ll(1e18)+9;
ll result = inf;
for (auto it : acc) {
setmin(result, get<2>(it));
}
printf("%lld\n", result);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Shik and Travel |
User |
kimiyuki |
Language |
C++14 (Clang 3.8.0) |
Score |
0 |
Code Size |
3251 Byte |
Status |
TLE |
Exec Time |
5257 ms |
Memory |
138380 KB |
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 |
3 ms |
384 KB |
001.txt |
AC |
3 ms |
384 KB |
002.txt |
AC |
3 ms |
384 KB |
003.txt |
AC |
3 ms |
384 KB |
004.txt |
AC |
3 ms |
384 KB |
005.txt |
AC |
3 ms |
384 KB |
006.txt |
AC |
3 ms |
384 KB |
007.txt |
AC |
3 ms |
384 KB |
008.txt |
AC |
3 ms |
384 KB |
009.txt |
AC |
3 ms |
384 KB |
010.txt |
AC |
127 ms |
8576 KB |
011.txt |
AC |
130 ms |
8576 KB |
012.txt |
AC |
131 ms |
8576 KB |
013.txt |
AC |
129 ms |
8576 KB |
014.txt |
AC |
129 ms |
8576 KB |
015.txt |
AC |
128 ms |
8576 KB |
016.txt |
AC |
136 ms |
8576 KB |
017.txt |
AC |
134 ms |
8576 KB |
018.txt |
AC |
135 ms |
8576 KB |
019.txt |
AC |
121 ms |
8576 KB |
020.txt |
AC |
129 ms |
8576 KB |
021.txt |
AC |
126 ms |
8576 KB |
022.txt |
AC |
129 ms |
8576 KB |
023.txt |
AC |
130 ms |
8576 KB |
024.txt |
AC |
129 ms |
8576 KB |
025.txt |
AC |
128 ms |
8576 KB |
026.txt |
AC |
70 ms |
8448 KB |
027.txt |
AC |
128 ms |
8576 KB |
028.txt |
AC |
70 ms |
8448 KB |
029.txt |
AC |
69 ms |
8448 KB |
030.txt |
AC |
90 ms |
8448 KB |
031.txt |
AC |
100 ms |
8448 KB |
032.txt |
AC |
91 ms |
8448 KB |
033.txt |
AC |
99 ms |
8448 KB |
034.txt |
AC |
95 ms |
8448 KB |
035.txt |
AC |
92 ms |
8448 KB |
036.txt |
AC |
91 ms |
8448 KB |
037.txt |
AC |
85 ms |
8448 KB |
038.txt |
AC |
91 ms |
8448 KB |
039.txt |
AC |
57 ms |
8448 KB |
040.txt |
TLE |
5256 ms |
70712 KB |
041.txt |
TLE |
5256 ms |
68664 KB |
042.txt |
TLE |
5256 ms |
70584 KB |
043.txt |
TLE |
5257 ms |
138380 KB |
044.txt |
AC |
85 ms |
36096 KB |
045.txt |
AC |
70 ms |
22272 KB |
046.txt |
AC |
200 ms |
26284 KB |
047.txt |
AC |
147 ms |
23512 KB |
048.txt |
AC |
244 ms |
31744 KB |
049.txt |
AC |
1 ms |
256 KB |
example0.txt |
AC |
1 ms |
256 KB |
example1.txt |
AC |
1 ms |
256 KB |
example2.txt |
AC |
1 ms |
256 KB |
example3.txt |
AC |
1 ms |
256 KB |