Submission #1453835
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))
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());
for (auto x_i : x) {
ll x1, x2, xmin; tie(x1, x2, xmin) = x_i;
y.emplace_back(x1 + value, x2 + value, xmin);
}
}
}
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;
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);
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
2017-07-26 05:26:22+0900
Task
E - Shik and Travel
User
kimiyuki
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2935 Byte
Status
TLE
Exec Time
5256 ms
Memory
83052 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:19:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int n; scanf("%d", &n);
^
./Main.cpp:22:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a, v; scanf("%d%d", &a, &v);
^
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
131 ms
8448 KB
011.txt
AC
132 ms
8448 KB
012.txt
AC
137 ms
8448 KB
013.txt
AC
131 ms
8448 KB
014.txt
AC
130 ms
8448 KB
015.txt
AC
131 ms
8448 KB
016.txt
AC
133 ms
8448 KB
017.txt
AC
133 ms
8448 KB
018.txt
AC
133 ms
8448 KB
019.txt
AC
121 ms
8448 KB
020.txt
AC
131 ms
8448 KB
021.txt
AC
129 ms
8448 KB
022.txt
AC
131 ms
8448 KB
023.txt
AC
131 ms
8448 KB
024.txt
AC
132 ms
8448 KB
025.txt
AC
131 ms
8448 KB
026.txt
AC
69 ms
8448 KB
027.txt
AC
131 ms
8448 KB
028.txt
AC
72 ms
8448 KB
029.txt
AC
71 ms
8448 KB
030.txt
AC
91 ms
8448 KB
031.txt
AC
100 ms
8448 KB
032.txt
AC
94 ms
8448 KB
033.txt
AC
100 ms
8448 KB
034.txt
AC
98 ms
8448 KB
035.txt
AC
93 ms
8448 KB
036.txt
AC
92 ms
8448 KB
037.txt
AC
89 ms
8448 KB
038.txt
AC
92 ms
8448 KB
039.txt
AC
63 ms
8448 KB
040.txt
TLE
5256 ms
57908 KB
041.txt
TLE
5256 ms
82580 KB
042.txt
TLE
5256 ms
59552 KB
043.txt
TLE
5256 ms
83052 KB
044.txt
AC
77 ms
32000 KB
045.txt
AC
72 ms
20224 KB
046.txt
AC
200 ms
23592 KB
047.txt
AC
149 ms
21204 KB
048.txt
AC
252 ms
28288 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