| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1047969 |
2024-08-07T19:08:26 Z |
manhlinh1501 |
Race (IOI11_race) |
C++17 |
|
270 ms |
105044 KB |
//#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 2e5 + 5;
const int oo32 = 2e9;
#define sz(a) (int)a.size()
int N, K;
vector<pii> adj[MAXN];
map<i64, int> dp[MAXN];
int ans = oo32;
void DFS(int u, i64 c = 0, int depth = 0, int p = -1) {
dp[u][c] = depth;
for(auto [v, w] : adj[u]) {
if(v == p) continue;
DFS(v, c + w, depth + 1, u);
if(dp[u].size() < dp[v].size()) swap(dp[u], dp[v]);
for(auto [x, y] : dp[v]) {
if(dp[u].find(c + K - (x - c)) != dp[u].end())
ans = min(ans, y + dp[u][c + K - (x - c)] - 2 * depth);
}
for(auto [x, y] : dp[v]) {
if(dp[u].find(x) != dp[u].end())
dp[u][x] = min(dp[u][x], y);
else dp[u][x] = y;
}
}
}
int best_path(int _N, int _K, int H[][2], int L[]) {
N = _N;
K = _K;
ans = oo32;
for(int i = 0; i < N - 1; i++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
u++;
v++;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
DFS(1);
return (ans == oo32 ? -1 : ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
18008 KB |
Output is correct |
| 2 |
Correct |
2 ms |
18168 KB |
Output is correct |
| 3 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 4 |
Correct |
2 ms |
18148 KB |
Output is correct |
| 5 |
Correct |
2 ms |
18008 KB |
Output is correct |
| 6 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 7 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 8 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 9 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 10 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 11 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 12 |
Correct |
3 ms |
18008 KB |
Output is correct |
| 13 |
Correct |
3 ms |
18012 KB |
Output is correct |
| 14 |
Correct |
3 ms |
18212 KB |
Output is correct |
| 15 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 16 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 17 |
Correct |
2 ms |
18104 KB |
Output is correct |
| 18 |
Correct |
3 ms |
18164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
18008 KB |
Output is correct |
| 2 |
Correct |
2 ms |
18168 KB |
Output is correct |
| 3 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 4 |
Correct |
2 ms |
18148 KB |
Output is correct |
| 5 |
Correct |
2 ms |
18008 KB |
Output is correct |
| 6 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 7 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 8 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 9 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 10 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 11 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 12 |
Correct |
3 ms |
18008 KB |
Output is correct |
| 13 |
Correct |
3 ms |
18012 KB |
Output is correct |
| 14 |
Correct |
3 ms |
18212 KB |
Output is correct |
| 15 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 16 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 17 |
Correct |
2 ms |
18104 KB |
Output is correct |
| 18 |
Correct |
3 ms |
18164 KB |
Output is correct |
| 19 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 20 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 21 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 22 |
Correct |
3 ms |
18296 KB |
Output is correct |
| 23 |
Correct |
3 ms |
18416 KB |
Output is correct |
| 24 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 25 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 26 |
Correct |
3 ms |
18440 KB |
Output is correct |
| 27 |
Correct |
2 ms |
18244 KB |
Output is correct |
| 28 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 29 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 30 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 31 |
Correct |
3 ms |
18264 KB |
Output is correct |
| 32 |
Correct |
3 ms |
18436 KB |
Output is correct |
| 33 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 34 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 35 |
Correct |
2 ms |
18268 KB |
Output is correct |
| 36 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 37 |
Correct |
3 ms |
18376 KB |
Output is correct |
| 38 |
Correct |
3 ms |
18268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
18008 KB |
Output is correct |
| 2 |
Correct |
2 ms |
18168 KB |
Output is correct |
| 3 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 4 |
Correct |
2 ms |
18148 KB |
Output is correct |
| 5 |
Correct |
2 ms |
18008 KB |
Output is correct |
| 6 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 7 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 8 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 9 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 10 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 11 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 12 |
Correct |
3 ms |
18008 KB |
Output is correct |
| 13 |
Correct |
3 ms |
18012 KB |
Output is correct |
| 14 |
Correct |
3 ms |
18212 KB |
Output is correct |
| 15 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 16 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 17 |
Correct |
2 ms |
18104 KB |
Output is correct |
| 18 |
Correct |
3 ms |
18164 KB |
Output is correct |
| 19 |
Correct |
65 ms |
40788 KB |
Output is correct |
| 20 |
Correct |
62 ms |
40784 KB |
Output is correct |
| 21 |
Correct |
66 ms |
40532 KB |
Output is correct |
| 22 |
Correct |
63 ms |
40272 KB |
Output is correct |
| 23 |
Correct |
89 ms |
53072 KB |
Output is correct |
| 24 |
Correct |
68 ms |
43600 KB |
Output is correct |
| 25 |
Correct |
53 ms |
41556 KB |
Output is correct |
| 26 |
Correct |
37 ms |
49744 KB |
Output is correct |
| 27 |
Correct |
102 ms |
49748 KB |
Output is correct |
| 28 |
Correct |
161 ms |
92032 KB |
Output is correct |
| 29 |
Correct |
157 ms |
90452 KB |
Output is correct |
| 30 |
Correct |
112 ms |
49748 KB |
Output is correct |
| 31 |
Correct |
108 ms |
49744 KB |
Output is correct |
| 32 |
Correct |
124 ms |
50008 KB |
Output is correct |
| 33 |
Correct |
127 ms |
54768 KB |
Output is correct |
| 34 |
Correct |
189 ms |
87632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
18008 KB |
Output is correct |
| 2 |
Correct |
2 ms |
18168 KB |
Output is correct |
| 3 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 4 |
Correct |
2 ms |
18148 KB |
Output is correct |
| 5 |
Correct |
2 ms |
18008 KB |
Output is correct |
| 6 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 7 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 8 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 9 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 10 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 11 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 12 |
Correct |
3 ms |
18008 KB |
Output is correct |
| 13 |
Correct |
3 ms |
18012 KB |
Output is correct |
| 14 |
Correct |
3 ms |
18212 KB |
Output is correct |
| 15 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 16 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 17 |
Correct |
2 ms |
18104 KB |
Output is correct |
| 18 |
Correct |
3 ms |
18164 KB |
Output is correct |
| 19 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 20 |
Correct |
2 ms |
18012 KB |
Output is correct |
| 21 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 22 |
Correct |
3 ms |
18296 KB |
Output is correct |
| 23 |
Correct |
3 ms |
18416 KB |
Output is correct |
| 24 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 25 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 26 |
Correct |
3 ms |
18440 KB |
Output is correct |
| 27 |
Correct |
2 ms |
18244 KB |
Output is correct |
| 28 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 29 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 30 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 31 |
Correct |
3 ms |
18264 KB |
Output is correct |
| 32 |
Correct |
3 ms |
18436 KB |
Output is correct |
| 33 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 34 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 35 |
Correct |
2 ms |
18268 KB |
Output is correct |
| 36 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 37 |
Correct |
3 ms |
18376 KB |
Output is correct |
| 38 |
Correct |
3 ms |
18268 KB |
Output is correct |
| 39 |
Correct |
65 ms |
40788 KB |
Output is correct |
| 40 |
Correct |
62 ms |
40784 KB |
Output is correct |
| 41 |
Correct |
66 ms |
40532 KB |
Output is correct |
| 42 |
Correct |
63 ms |
40272 KB |
Output is correct |
| 43 |
Correct |
89 ms |
53072 KB |
Output is correct |
| 44 |
Correct |
68 ms |
43600 KB |
Output is correct |
| 45 |
Correct |
53 ms |
41556 KB |
Output is correct |
| 46 |
Correct |
37 ms |
49744 KB |
Output is correct |
| 47 |
Correct |
102 ms |
49748 KB |
Output is correct |
| 48 |
Correct |
161 ms |
92032 KB |
Output is correct |
| 49 |
Correct |
157 ms |
90452 KB |
Output is correct |
| 50 |
Correct |
112 ms |
49748 KB |
Output is correct |
| 51 |
Correct |
108 ms |
49744 KB |
Output is correct |
| 52 |
Correct |
124 ms |
50008 KB |
Output is correct |
| 53 |
Correct |
127 ms |
54768 KB |
Output is correct |
| 54 |
Correct |
189 ms |
87632 KB |
Output is correct |
| 55 |
Correct |
10 ms |
21084 KB |
Output is correct |
| 56 |
Correct |
6 ms |
19820 KB |
Output is correct |
| 57 |
Correct |
36 ms |
38232 KB |
Output is correct |
| 58 |
Correct |
35 ms |
31444 KB |
Output is correct |
| 59 |
Correct |
57 ms |
56008 KB |
Output is correct |
| 60 |
Correct |
157 ms |
90728 KB |
Output is correct |
| 61 |
Correct |
126 ms |
53268 KB |
Output is correct |
| 62 |
Correct |
99 ms |
49988 KB |
Output is correct |
| 63 |
Correct |
129 ms |
49940 KB |
Output is correct |
| 64 |
Correct |
266 ms |
105044 KB |
Output is correct |
| 65 |
Correct |
270 ms |
103504 KB |
Output is correct |
| 66 |
Correct |
169 ms |
86352 KB |
Output is correct |
| 67 |
Correct |
107 ms |
44228 KB |
Output is correct |
| 68 |
Correct |
222 ms |
66828 KB |
Output is correct |
| 69 |
Correct |
230 ms |
72016 KB |
Output is correct |
| 70 |
Correct |
224 ms |
65008 KB |
Output is correct |
