| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 849175 |
2023-09-14T08:27:03 Z |
abcvuitunggio |
Race (IOI11_race) |
C++17 |
|
315 ms |
80208 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector <pair <int, int>> ke[200001];
map <long long, long long> mp[200001];
long long k,len[200001],res=1e9,d[200001];
void dfs(int u, int p){
int bigchild=-1,sz=0;
for (auto [v,w]:ke[u])
if (v!=p){
d[v]=d[u]+1;
len[v]=len[u]+w;
dfs(v,u);
if (mp[v].size()>sz){
sz=mp[v].size();
bigchild=v;
}
}
if (bigchild!=-1)
swap(mp[u],mp[bigchild]);
for (auto [v,w]:ke[u]){
if (v!=bigchild){
for (auto [l,h]:mp[v])
if (mp[u].count(k+len[u]*2-l))
res=min(res,mp[u][k+len[u]*2-l]+h-d[u]*2);
for (auto [l,h]:mp[v])
if (!mp[u].count(l))
mp[u][l]=h;
else
mp[u][l]=min(mp[u][l],h);
mp[v].clear();
}
}
if (mp[u].count(k+len[u]))
res=min(res,mp[u][k+len[u]]-d[u]);
if (!mp[u].count(len[u]))
mp[u][len[u]]=d[u];
else
mp[u][len[u]]=min(mp[u][len[u]],d[u]);
}
int best_path(int N, int K, int H[][2], int L[]){
k=K;
for (int i=0;i<N-1;i++){
ke[H[i][0]].push_back({H[i][1],L[i]});
ke[H[i][1]].push_back({H[i][0],L[i]});
}
dfs(0,0);
return (res>N?-1:res);
}
Compilation message
race.cpp: In function 'void dfs(int, int)':
race.cpp:14:29: warning: comparison of integer expressions of different signedness: 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
14 | if (mp[v].size()>sz){
| ~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 4 |
Correct |
4 ms |
19032 KB |
Output is correct |
| 5 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 6 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 7 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 8 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 9 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 10 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 11 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 12 |
Correct |
4 ms |
19552 KB |
Output is correct |
| 13 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 14 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 15 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 16 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 17 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 18 |
Correct |
4 ms |
19288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 4 |
Correct |
4 ms |
19032 KB |
Output is correct |
| 5 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 6 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 7 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 8 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 9 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 10 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 11 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 12 |
Correct |
4 ms |
19552 KB |
Output is correct |
| 13 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 14 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 15 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 16 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 17 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 18 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 19 |
Correct |
3 ms |
19032 KB |
Output is correct |
| 20 |
Correct |
4 ms |
19032 KB |
Output is correct |
| 21 |
Correct |
5 ms |
19288 KB |
Output is correct |
| 22 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 23 |
Correct |
5 ms |
19276 KB |
Output is correct |
| 24 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 25 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 26 |
Correct |
5 ms |
19288 KB |
Output is correct |
| 27 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 28 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 29 |
Correct |
5 ms |
19288 KB |
Output is correct |
| 30 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 31 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 32 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 33 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 34 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 35 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 36 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 37 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 38 |
Correct |
4 ms |
19292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 4 |
Correct |
4 ms |
19032 KB |
Output is correct |
| 5 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 6 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 7 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 8 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 9 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 10 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 11 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 12 |
Correct |
4 ms |
19552 KB |
Output is correct |
| 13 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 14 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 15 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 16 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 17 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 18 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 19 |
Correct |
75 ms |
26344 KB |
Output is correct |
| 20 |
Correct |
64 ms |
26200 KB |
Output is correct |
| 21 |
Correct |
64 ms |
26192 KB |
Output is correct |
| 22 |
Correct |
78 ms |
26192 KB |
Output is correct |
| 23 |
Correct |
95 ms |
26704 KB |
Output is correct |
| 24 |
Correct |
79 ms |
26448 KB |
Output is correct |
| 25 |
Correct |
83 ms |
36176 KB |
Output is correct |
| 26 |
Correct |
45 ms |
44496 KB |
Output is correct |
| 27 |
Correct |
125 ms |
37848 KB |
Output is correct |
| 28 |
Correct |
204 ms |
80208 KB |
Output is correct |
| 29 |
Correct |
194 ms |
77904 KB |
Output is correct |
| 30 |
Correct |
126 ms |
37836 KB |
Output is correct |
| 31 |
Correct |
141 ms |
37712 KB |
Output is correct |
| 32 |
Correct |
152 ms |
37812 KB |
Output is correct |
| 33 |
Correct |
157 ms |
31092 KB |
Output is correct |
| 34 |
Correct |
240 ms |
43672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 4 |
Correct |
4 ms |
19032 KB |
Output is correct |
| 5 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 6 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 7 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 8 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 9 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 10 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 11 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 12 |
Correct |
4 ms |
19552 KB |
Output is correct |
| 13 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 14 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 15 |
Correct |
3 ms |
19288 KB |
Output is correct |
| 16 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 17 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 18 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 19 |
Correct |
3 ms |
19032 KB |
Output is correct |
| 20 |
Correct |
4 ms |
19032 KB |
Output is correct |
| 21 |
Correct |
5 ms |
19288 KB |
Output is correct |
| 22 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 23 |
Correct |
5 ms |
19276 KB |
Output is correct |
| 24 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 25 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 26 |
Correct |
5 ms |
19288 KB |
Output is correct |
| 27 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 28 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 29 |
Correct |
5 ms |
19288 KB |
Output is correct |
| 30 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 31 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 32 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 33 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 34 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 35 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 36 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 37 |
Correct |
4 ms |
19288 KB |
Output is correct |
| 38 |
Correct |
4 ms |
19292 KB |
Output is correct |
| 39 |
Correct |
75 ms |
26344 KB |
Output is correct |
| 40 |
Correct |
64 ms |
26200 KB |
Output is correct |
| 41 |
Correct |
64 ms |
26192 KB |
Output is correct |
| 42 |
Correct |
78 ms |
26192 KB |
Output is correct |
| 43 |
Correct |
95 ms |
26704 KB |
Output is correct |
| 44 |
Correct |
79 ms |
26448 KB |
Output is correct |
| 45 |
Correct |
83 ms |
36176 KB |
Output is correct |
| 46 |
Correct |
45 ms |
44496 KB |
Output is correct |
| 47 |
Correct |
125 ms |
37848 KB |
Output is correct |
| 48 |
Correct |
204 ms |
80208 KB |
Output is correct |
| 49 |
Correct |
194 ms |
77904 KB |
Output is correct |
| 50 |
Correct |
126 ms |
37836 KB |
Output is correct |
| 51 |
Correct |
141 ms |
37712 KB |
Output is correct |
| 52 |
Correct |
152 ms |
37812 KB |
Output is correct |
| 53 |
Correct |
157 ms |
31092 KB |
Output is correct |
| 54 |
Correct |
240 ms |
43672 KB |
Output is correct |
| 55 |
Correct |
13 ms |
20056 KB |
Output is correct |
| 56 |
Correct |
8 ms |
19544 KB |
Output is correct |
| 57 |
Correct |
42 ms |
27220 KB |
Output is correct |
| 58 |
Correct |
46 ms |
33476 KB |
Output is correct |
| 59 |
Correct |
71 ms |
51280 KB |
Output is correct |
| 60 |
Correct |
193 ms |
79696 KB |
Output is correct |
| 61 |
Correct |
171 ms |
40596 KB |
Output is correct |
| 62 |
Correct |
132 ms |
38596 KB |
Output is correct |
| 63 |
Correct |
161 ms |
38700 KB |
Output is correct |
| 64 |
Correct |
315 ms |
40528 KB |
Output is correct |
| 65 |
Correct |
305 ms |
45904 KB |
Output is correct |
| 66 |
Correct |
216 ms |
75180 KB |
Output is correct |
| 67 |
Correct |
133 ms |
45244 KB |
Output is correct |
| 68 |
Correct |
248 ms |
44376 KB |
Output is correct |
| 69 |
Correct |
246 ms |
44952 KB |
Output is correct |
| 70 |
Correct |
218 ms |
43416 KB |
Output is correct |
