| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 487516 |
2021-11-15T21:47:40 Z |
thiago_bastos |
Race (IOI11_race) |
C++17 |
|
451 ms |
109644 KB |
#include "race.h"
#include <vector>
#include <set>
#include <utility>
#include <functional>
using namespace std;
using ii = pair<int, int>;
using i64 = long long;
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<ii>> g(N);
vector<i64> pre(N);
vector<set<pair<i64, int>>> S(N);
int ans = N + 1;
for(int i = 0; i < N - 1; ++i) {
int u = H[i][0], v = H[i][1];
g[u].emplace_back(v, L[i]);
g[v].emplace_back(u, L[i]);
}
pre[0] = 0;
function<void(int, int, int)> dfs = [&](int u, int p, int h) {
S[u].insert(make_pair(pre[u], h));
for(auto [v, w] : g[u]) {
if(v == p) continue;
pre[v] = pre[u] + w;
dfs(v, u, h + 1);
if(S[v].size() > S[u].size()) swap(S[u], S[v]);
for(auto [cost, depth] : S[v]) {
i64 X = K - cost + 2 * pre[u];
auto k = S[u].lower_bound(make_pair(X, -1));
if(k == S[u].end() || k->first != X) continue;
ans = min(ans, depth + k->second - 2 * h);
}
for(auto [cost, depth] : S[v]) S[u].insert(make_pair(cost, depth));
}
};
dfs(0, 0, 0);
if(ans == N + 1) ans = -1;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
0 ms |
336 KB |
Output is correct |
| 8 |
Correct |
0 ms |
336 KB |
Output is correct |
| 9 |
Correct |
0 ms |
336 KB |
Output is correct |
| 10 |
Correct |
0 ms |
336 KB |
Output is correct |
| 11 |
Correct |
0 ms |
336 KB |
Output is correct |
| 12 |
Correct |
0 ms |
336 KB |
Output is correct |
| 13 |
Correct |
0 ms |
336 KB |
Output is correct |
| 14 |
Correct |
0 ms |
300 KB |
Output is correct |
| 15 |
Correct |
0 ms |
336 KB |
Output is correct |
| 16 |
Correct |
0 ms |
336 KB |
Output is correct |
| 17 |
Correct |
0 ms |
336 KB |
Output is correct |
| 18 |
Correct |
0 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
0 ms |
336 KB |
Output is correct |
| 8 |
Correct |
0 ms |
336 KB |
Output is correct |
| 9 |
Correct |
0 ms |
336 KB |
Output is correct |
| 10 |
Correct |
0 ms |
336 KB |
Output is correct |
| 11 |
Correct |
0 ms |
336 KB |
Output is correct |
| 12 |
Correct |
0 ms |
336 KB |
Output is correct |
| 13 |
Correct |
0 ms |
336 KB |
Output is correct |
| 14 |
Correct |
0 ms |
300 KB |
Output is correct |
| 15 |
Correct |
0 ms |
336 KB |
Output is correct |
| 16 |
Correct |
0 ms |
336 KB |
Output is correct |
| 17 |
Correct |
0 ms |
336 KB |
Output is correct |
| 18 |
Correct |
0 ms |
336 KB |
Output is correct |
| 19 |
Correct |
0 ms |
208 KB |
Output is correct |
| 20 |
Correct |
0 ms |
208 KB |
Output is correct |
| 21 |
Correct |
1 ms |
592 KB |
Output is correct |
| 22 |
Correct |
2 ms |
592 KB |
Output is correct |
| 23 |
Correct |
2 ms |
560 KB |
Output is correct |
| 24 |
Correct |
1 ms |
592 KB |
Output is correct |
| 25 |
Correct |
1 ms |
592 KB |
Output is correct |
| 26 |
Correct |
1 ms |
696 KB |
Output is correct |
| 27 |
Correct |
1 ms |
464 KB |
Output is correct |
| 28 |
Correct |
2 ms |
592 KB |
Output is correct |
| 29 |
Correct |
1 ms |
592 KB |
Output is correct |
| 30 |
Correct |
1 ms |
592 KB |
Output is correct |
| 31 |
Correct |
2 ms |
592 KB |
Output is correct |
| 32 |
Correct |
1 ms |
592 KB |
Output is correct |
| 33 |
Correct |
1 ms |
592 KB |
Output is correct |
| 34 |
Correct |
1 ms |
556 KB |
Output is correct |
| 35 |
Correct |
1 ms |
592 KB |
Output is correct |
| 36 |
Correct |
1 ms |
592 KB |
Output is correct |
| 37 |
Correct |
1 ms |
592 KB |
Output is correct |
| 38 |
Correct |
1 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
0 ms |
336 KB |
Output is correct |
| 8 |
Correct |
0 ms |
336 KB |
Output is correct |
| 9 |
Correct |
0 ms |
336 KB |
Output is correct |
| 10 |
Correct |
0 ms |
336 KB |
Output is correct |
| 11 |
Correct |
0 ms |
336 KB |
Output is correct |
| 12 |
Correct |
0 ms |
336 KB |
Output is correct |
| 13 |
Correct |
0 ms |
336 KB |
Output is correct |
| 14 |
Correct |
0 ms |
300 KB |
Output is correct |
| 15 |
Correct |
0 ms |
336 KB |
Output is correct |
| 16 |
Correct |
0 ms |
336 KB |
Output is correct |
| 17 |
Correct |
0 ms |
336 KB |
Output is correct |
| 18 |
Correct |
0 ms |
336 KB |
Output is correct |
| 19 |
Correct |
143 ms |
34928 KB |
Output is correct |
| 20 |
Correct |
145 ms |
34624 KB |
Output is correct |
| 21 |
Correct |
142 ms |
34120 KB |
Output is correct |
| 22 |
Correct |
144 ms |
32584 KB |
Output is correct |
| 23 |
Correct |
185 ms |
47088 KB |
Output is correct |
| 24 |
Correct |
140 ms |
33704 KB |
Output is correct |
| 25 |
Correct |
128 ms |
38984 KB |
Output is correct |
| 26 |
Correct |
88 ms |
45000 KB |
Output is correct |
| 27 |
Correct |
181 ms |
50908 KB |
Output is correct |
| 28 |
Correct |
327 ms |
90244 KB |
Output is correct |
| 29 |
Correct |
318 ms |
88348 KB |
Output is correct |
| 30 |
Correct |
187 ms |
50852 KB |
Output is correct |
| 31 |
Correct |
185 ms |
50800 KB |
Output is correct |
| 32 |
Correct |
249 ms |
50956 KB |
Output is correct |
| 33 |
Correct |
230 ms |
52708 KB |
Output is correct |
| 34 |
Correct |
333 ms |
85724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
0 ms |
336 KB |
Output is correct |
| 8 |
Correct |
0 ms |
336 KB |
Output is correct |
| 9 |
Correct |
0 ms |
336 KB |
Output is correct |
| 10 |
Correct |
0 ms |
336 KB |
Output is correct |
| 11 |
Correct |
0 ms |
336 KB |
Output is correct |
| 12 |
Correct |
0 ms |
336 KB |
Output is correct |
| 13 |
Correct |
0 ms |
336 KB |
Output is correct |
| 14 |
Correct |
0 ms |
300 KB |
Output is correct |
| 15 |
Correct |
0 ms |
336 KB |
Output is correct |
| 16 |
Correct |
0 ms |
336 KB |
Output is correct |
| 17 |
Correct |
0 ms |
336 KB |
Output is correct |
| 18 |
Correct |
0 ms |
336 KB |
Output is correct |
| 19 |
Correct |
0 ms |
208 KB |
Output is correct |
| 20 |
Correct |
0 ms |
208 KB |
Output is correct |
| 21 |
Correct |
1 ms |
592 KB |
Output is correct |
| 22 |
Correct |
2 ms |
592 KB |
Output is correct |
| 23 |
Correct |
2 ms |
560 KB |
Output is correct |
| 24 |
Correct |
1 ms |
592 KB |
Output is correct |
| 25 |
Correct |
1 ms |
592 KB |
Output is correct |
| 26 |
Correct |
1 ms |
696 KB |
Output is correct |
| 27 |
Correct |
1 ms |
464 KB |
Output is correct |
| 28 |
Correct |
2 ms |
592 KB |
Output is correct |
| 29 |
Correct |
1 ms |
592 KB |
Output is correct |
| 30 |
Correct |
1 ms |
592 KB |
Output is correct |
| 31 |
Correct |
2 ms |
592 KB |
Output is correct |
| 32 |
Correct |
1 ms |
592 KB |
Output is correct |
| 33 |
Correct |
1 ms |
592 KB |
Output is correct |
| 34 |
Correct |
1 ms |
556 KB |
Output is correct |
| 35 |
Correct |
1 ms |
592 KB |
Output is correct |
| 36 |
Correct |
1 ms |
592 KB |
Output is correct |
| 37 |
Correct |
1 ms |
592 KB |
Output is correct |
| 38 |
Correct |
1 ms |
632 KB |
Output is correct |
| 39 |
Correct |
143 ms |
34928 KB |
Output is correct |
| 40 |
Correct |
145 ms |
34624 KB |
Output is correct |
| 41 |
Correct |
142 ms |
34120 KB |
Output is correct |
| 42 |
Correct |
144 ms |
32584 KB |
Output is correct |
| 43 |
Correct |
185 ms |
47088 KB |
Output is correct |
| 44 |
Correct |
140 ms |
33704 KB |
Output is correct |
| 45 |
Correct |
128 ms |
38984 KB |
Output is correct |
| 46 |
Correct |
88 ms |
45000 KB |
Output is correct |
| 47 |
Correct |
181 ms |
50908 KB |
Output is correct |
| 48 |
Correct |
327 ms |
90244 KB |
Output is correct |
| 49 |
Correct |
318 ms |
88348 KB |
Output is correct |
| 50 |
Correct |
187 ms |
50852 KB |
Output is correct |
| 51 |
Correct |
185 ms |
50800 KB |
Output is correct |
| 52 |
Correct |
249 ms |
50956 KB |
Output is correct |
| 53 |
Correct |
230 ms |
52708 KB |
Output is correct |
| 54 |
Correct |
333 ms |
85724 KB |
Output is correct |
| 55 |
Correct |
13 ms |
4432 KB |
Output is correct |
| 56 |
Correct |
8 ms |
3152 KB |
Output is correct |
| 57 |
Correct |
88 ms |
29356 KB |
Output is correct |
| 58 |
Correct |
44 ms |
20412 KB |
Output is correct |
| 59 |
Correct |
84 ms |
45072 KB |
Output is correct |
| 60 |
Correct |
294 ms |
88840 KB |
Output is correct |
| 61 |
Correct |
238 ms |
56576 KB |
Output is correct |
| 62 |
Correct |
182 ms |
50888 KB |
Output is correct |
| 63 |
Correct |
251 ms |
51008 KB |
Output is correct |
| 64 |
Correct |
451 ms |
109644 KB |
Output is correct |
| 65 |
Correct |
444 ms |
101448 KB |
Output is correct |
| 66 |
Correct |
307 ms |
84288 KB |
Output is correct |
| 67 |
Correct |
186 ms |
42444 KB |
Output is correct |
| 68 |
Correct |
326 ms |
66240 KB |
Output is correct |
| 69 |
Correct |
347 ms |
72064 KB |
Output is correct |
| 70 |
Correct |
335 ms |
63360 KB |
Output is correct |
