| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1105633 |
2024-10-27T06:54:00 Z |
anngela |
Race (IOI11_race) |
C++17 |
|
228 ms |
38364 KB |
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5, W = 1e6+5, inf = 1e9;
int n, k, sz[N];
int hmin[W], ans;
bool del[N];
vector<pair<int,int>> adj[N];
int Size(int x, int t)
{
sz[x] = 1;
for (auto [y, _] : adj[x])
{
if (y == t || del[y]) continue;
sz[x] += Size(y, x);
}
return sz[x];
}
int Centroid(int x, int size, int t = -1)
{
for (auto [y, _] : adj[x])
{
if (y == t || del[y]) continue;
if (2 * sz[y] > size)
return Centroid(y, size, x);
}
return x;
}
queue<int> q;
stack<pair<int, int>> path;
void dfs(int x, int t, int we = 0, int d = 0)
{
if (hmin[k - we] != inf)
ans = min(ans, hmin[k - we] + d);
for (auto [y, w] : adj[x])
{
if (del[y] || y == t) continue;
if (we + w <= k && d + 1 <= ans)
dfs(y, x, we + w, d + 1);
if (t == -1)
{
while (!path.empty())
{
auto [dist, h] = path.top();
path.pop();
hmin[dist] = min(hmin[dist], h);
}
}
}
if (t != -1)
{
q.push(we);
path.emplace(we, d);
}
else
{
while (!q.empty())
{
int dist = q.front();
q.pop();
hmin[dist] = inf;
}
}
}
void Decompose(int x)
{
x = Centroid(x, Size(x, -1));
del[x] = true;
dfs(x, -1);
for (auto e : adj[x])
{
int y = e.fi;
if(!del[y]) Decompose(y);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for (int i = 0; i < n-1; i++)
{
int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
ans = inf;
for(int i = 1; i <= k; i++){
hmin[i] = inf;
}
Decompose(1);
return (ans == inf ? -1 : ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 6 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 7 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 8 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 10 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 11 |
Correct |
2 ms |
10748 KB |
Output is correct |
| 12 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 13 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 14 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 15 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 17 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 18 |
Correct |
3 ms |
10576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 6 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 7 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 8 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 10 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 11 |
Correct |
2 ms |
10748 KB |
Output is correct |
| 12 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 13 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 14 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 15 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 17 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 18 |
Correct |
3 ms |
10576 KB |
Output is correct |
| 19 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 20 |
Correct |
2 ms |
10768 KB |
Output is correct |
| 21 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 22 |
Correct |
3 ms |
12792 KB |
Output is correct |
| 23 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 24 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 25 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 26 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 27 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 28 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 29 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 30 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 31 |
Correct |
3 ms |
12816 KB |
Output is correct |
| 32 |
Correct |
4 ms |
12624 KB |
Output is correct |
| 33 |
Correct |
4 ms |
12624 KB |
Output is correct |
| 34 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 35 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 36 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 37 |
Correct |
2 ms |
12624 KB |
Output is correct |
| 38 |
Correct |
3 ms |
12624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 6 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 7 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 8 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 10 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 11 |
Correct |
2 ms |
10748 KB |
Output is correct |
| 12 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 13 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 14 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 15 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 17 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 18 |
Correct |
3 ms |
10576 KB |
Output is correct |
| 19 |
Correct |
61 ms |
16848 KB |
Output is correct |
| 20 |
Correct |
60 ms |
18256 KB |
Output is correct |
| 21 |
Correct |
81 ms |
18248 KB |
Output is correct |
| 22 |
Correct |
63 ms |
18508 KB |
Output is correct |
| 23 |
Correct |
46 ms |
18512 KB |
Output is correct |
| 24 |
Correct |
37 ms |
18512 KB |
Output is correct |
| 25 |
Correct |
79 ms |
21072 KB |
Output is correct |
| 26 |
Correct |
68 ms |
24656 KB |
Output is correct |
| 27 |
Correct |
94 ms |
24136 KB |
Output is correct |
| 28 |
Correct |
158 ms |
35400 KB |
Output is correct |
| 29 |
Correct |
164 ms |
34376 KB |
Output is correct |
| 30 |
Correct |
103 ms |
24136 KB |
Output is correct |
| 31 |
Correct |
98 ms |
24136 KB |
Output is correct |
| 32 |
Correct |
106 ms |
24296 KB |
Output is correct |
| 33 |
Correct |
119 ms |
22856 KB |
Output is correct |
| 34 |
Correct |
113 ms |
23760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 6 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 7 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 8 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 10 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 11 |
Correct |
2 ms |
10748 KB |
Output is correct |
| 12 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 13 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 14 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 15 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 17 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 18 |
Correct |
3 ms |
10576 KB |
Output is correct |
| 19 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 20 |
Correct |
2 ms |
10768 KB |
Output is correct |
| 21 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 22 |
Correct |
3 ms |
12792 KB |
Output is correct |
| 23 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 24 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 25 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 26 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 27 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 28 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 29 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 30 |
Correct |
2 ms |
10576 KB |
Output is correct |
| 31 |
Correct |
3 ms |
12816 KB |
Output is correct |
| 32 |
Correct |
4 ms |
12624 KB |
Output is correct |
| 33 |
Correct |
4 ms |
12624 KB |
Output is correct |
| 34 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 35 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 36 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 37 |
Correct |
2 ms |
12624 KB |
Output is correct |
| 38 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 39 |
Correct |
61 ms |
16848 KB |
Output is correct |
| 40 |
Correct |
60 ms |
18256 KB |
Output is correct |
| 41 |
Correct |
81 ms |
18248 KB |
Output is correct |
| 42 |
Correct |
63 ms |
18508 KB |
Output is correct |
| 43 |
Correct |
46 ms |
18512 KB |
Output is correct |
| 44 |
Correct |
37 ms |
18512 KB |
Output is correct |
| 45 |
Correct |
79 ms |
21072 KB |
Output is correct |
| 46 |
Correct |
68 ms |
24656 KB |
Output is correct |
| 47 |
Correct |
94 ms |
24136 KB |
Output is correct |
| 48 |
Correct |
158 ms |
35400 KB |
Output is correct |
| 49 |
Correct |
164 ms |
34376 KB |
Output is correct |
| 50 |
Correct |
103 ms |
24136 KB |
Output is correct |
| 51 |
Correct |
98 ms |
24136 KB |
Output is correct |
| 52 |
Correct |
106 ms |
24296 KB |
Output is correct |
| 53 |
Correct |
119 ms |
22856 KB |
Output is correct |
| 54 |
Correct |
113 ms |
23760 KB |
Output is correct |
| 55 |
Correct |
7 ms |
11088 KB |
Output is correct |
| 56 |
Correct |
8 ms |
11344 KB |
Output is correct |
| 57 |
Correct |
51 ms |
19064 KB |
Output is correct |
| 58 |
Correct |
27 ms |
18628 KB |
Output is correct |
| 59 |
Correct |
67 ms |
24656 KB |
Output is correct |
| 60 |
Correct |
228 ms |
38364 KB |
Output is correct |
| 61 |
Correct |
103 ms |
24304 KB |
Output is correct |
| 62 |
Correct |
126 ms |
27224 KB |
Output is correct |
| 63 |
Correct |
132 ms |
27208 KB |
Output is correct |
| 64 |
Correct |
186 ms |
27720 KB |
Output is correct |
| 65 |
Correct |
106 ms |
24904 KB |
Output is correct |
| 66 |
Correct |
197 ms |
34752 KB |
Output is correct |
| 67 |
Correct |
68 ms |
28344 KB |
Output is correct |
| 68 |
Correct |
115 ms |
27224 KB |
Output is correct |
| 69 |
Correct |
104 ms |
27208 KB |
Output is correct |
| 70 |
Correct |
96 ms |
26616 KB |
Output is correct |
