# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
400197 |
2021-05-07T14:38:23 Z |
MOUF_MAHMALAT |
Race (IOI11_race) |
C++14 |
|
1997 ms |
48796 KB |
#include "race.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef int ll;
vector<vector<pair<ll,ll> > >v;
ll x,y,p[200009],k,ans=1e7;
bool b[200009];
deque<ll>dq;
map<ll,ll>op;
void dfs(ll d,ll pp)
{
p[d]=1;
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
dfs(z.f,d);
p[d]+=p[z.f];
}
}
ll center(ll d,ll pp)
{
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
if(p[z.f]*2>y)
return center(z.f,d);
}
return d;
}
void add(ll d,ll pp,ll sum,ll h)
{
if(sum>k)
return;
if(op[k-sum]||sum==k)
ans=min(ans,op[k-sum]+h);
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
add(z.f,d,sum+z.s,h+1);
}
}
void ok(ll d,ll pp,ll sum,ll h)
{
if(op[sum])
op[sum]=min(op[sum],h);
else
op[sum]=h;
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
ok(z.f,d,sum+z.s,h+1);
}
}
ll best_path(ll n, ll K, ll H[][2], ll co[])
{
k=K;
if(k==0)
return 0;
v.resize(n);
for(ll i=0; i<n-1; i++)
{
x=H[i][0], y=H[i][1];
v[x].push_back({y,co[i]});
v[y].push_back({x,co[i]});
}
dq.push_back(0);
while(dq.size())
{
x=dq.front();
dq.pop_front();
dfs(x,-1);
y=p[x];
x=center(x,-1);
op.clear();
b[x]=1;
for(auto z:v[x])
{
if(b[z.f])
continue;
add(z.f,x,z.s,1);
ok(z.f,x,z.s,1);
dq.push_back(z.f);
}
}
if(ans>=n)
ans=-1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
308 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
308 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
3 ms |
332 KB |
Output is correct |
22 |
Correct |
3 ms |
332 KB |
Output is correct |
23 |
Correct |
3 ms |
332 KB |
Output is correct |
24 |
Correct |
3 ms |
460 KB |
Output is correct |
25 |
Correct |
3 ms |
444 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
3 ms |
460 KB |
Output is correct |
29 |
Correct |
3 ms |
464 KB |
Output is correct |
30 |
Correct |
3 ms |
460 KB |
Output is correct |
31 |
Correct |
3 ms |
460 KB |
Output is correct |
32 |
Correct |
3 ms |
444 KB |
Output is correct |
33 |
Correct |
4 ms |
460 KB |
Output is correct |
34 |
Correct |
3 ms |
460 KB |
Output is correct |
35 |
Correct |
3 ms |
460 KB |
Output is correct |
36 |
Correct |
3 ms |
460 KB |
Output is correct |
37 |
Correct |
3 ms |
460 KB |
Output is correct |
38 |
Correct |
3 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
308 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
334 ms |
8284 KB |
Output is correct |
20 |
Correct |
318 ms |
8248 KB |
Output is correct |
21 |
Correct |
353 ms |
8316 KB |
Output is correct |
22 |
Correct |
327 ms |
8388 KB |
Output is correct |
23 |
Correct |
343 ms |
8676 KB |
Output is correct |
24 |
Correct |
164 ms |
8732 KB |
Output is correct |
25 |
Correct |
259 ms |
13460 KB |
Output is correct |
26 |
Correct |
134 ms |
15608 KB |
Output is correct |
27 |
Correct |
428 ms |
16404 KB |
Output is correct |
28 |
Correct |
1006 ms |
39924 KB |
Output is correct |
29 |
Correct |
1043 ms |
38516 KB |
Output is correct |
30 |
Correct |
436 ms |
16324 KB |
Output is correct |
31 |
Correct |
428 ms |
16564 KB |
Output is correct |
32 |
Correct |
556 ms |
16376 KB |
Output is correct |
33 |
Correct |
639 ms |
15172 KB |
Output is correct |
34 |
Correct |
997 ms |
24384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
308 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
3 ms |
332 KB |
Output is correct |
22 |
Correct |
3 ms |
332 KB |
Output is correct |
23 |
Correct |
3 ms |
332 KB |
Output is correct |
24 |
Correct |
3 ms |
460 KB |
Output is correct |
25 |
Correct |
3 ms |
444 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
3 ms |
460 KB |
Output is correct |
29 |
Correct |
3 ms |
464 KB |
Output is correct |
30 |
Correct |
3 ms |
460 KB |
Output is correct |
31 |
Correct |
3 ms |
460 KB |
Output is correct |
32 |
Correct |
3 ms |
444 KB |
Output is correct |
33 |
Correct |
4 ms |
460 KB |
Output is correct |
34 |
Correct |
3 ms |
460 KB |
Output is correct |
35 |
Correct |
3 ms |
460 KB |
Output is correct |
36 |
Correct |
3 ms |
460 KB |
Output is correct |
37 |
Correct |
3 ms |
460 KB |
Output is correct |
38 |
Correct |
3 ms |
460 KB |
Output is correct |
39 |
Correct |
334 ms |
8284 KB |
Output is correct |
40 |
Correct |
318 ms |
8248 KB |
Output is correct |
41 |
Correct |
353 ms |
8316 KB |
Output is correct |
42 |
Correct |
327 ms |
8388 KB |
Output is correct |
43 |
Correct |
343 ms |
8676 KB |
Output is correct |
44 |
Correct |
164 ms |
8732 KB |
Output is correct |
45 |
Correct |
259 ms |
13460 KB |
Output is correct |
46 |
Correct |
134 ms |
15608 KB |
Output is correct |
47 |
Correct |
428 ms |
16404 KB |
Output is correct |
48 |
Correct |
1006 ms |
39924 KB |
Output is correct |
49 |
Correct |
1043 ms |
38516 KB |
Output is correct |
50 |
Correct |
436 ms |
16324 KB |
Output is correct |
51 |
Correct |
428 ms |
16564 KB |
Output is correct |
52 |
Correct |
556 ms |
16376 KB |
Output is correct |
53 |
Correct |
639 ms |
15172 KB |
Output is correct |
54 |
Correct |
997 ms |
24384 KB |
Output is correct |
55 |
Correct |
31 ms |
1492 KB |
Output is correct |
56 |
Correct |
20 ms |
1152 KB |
Output is correct |
57 |
Correct |
204 ms |
9680 KB |
Output is correct |
58 |
Correct |
53 ms |
9656 KB |
Output is correct |
59 |
Correct |
465 ms |
23368 KB |
Output is correct |
60 |
Correct |
1568 ms |
48796 KB |
Output is correct |
61 |
Correct |
525 ms |
20292 KB |
Output is correct |
62 |
Correct |
505 ms |
19096 KB |
Output is correct |
63 |
Correct |
660 ms |
19108 KB |
Output is correct |
64 |
Correct |
1997 ms |
28356 KB |
Output is correct |
65 |
Correct |
1058 ms |
29252 KB |
Output is correct |
66 |
Correct |
1325 ms |
39236 KB |
Output is correct |
67 |
Correct |
159 ms |
20384 KB |
Output is correct |
68 |
Correct |
796 ms |
31036 KB |
Output is correct |
69 |
Correct |
784 ms |
31156 KB |
Output is correct |
70 |
Correct |
680 ms |
29764 KB |
Output is correct |