# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
403774 |
2021-05-13T12:38:39 Z |
Newtech66 |
Race (IOI11_race) |
C++17 |
|
1431 ms |
43460 KB |
#include "race.h"
#include<bits/stdc++.h>
#define MAXN 200000
using namespace std;
vector<vector<pair<int,int> > > g(MAXN);
vector<int> subsz(MAXN);
bitset<MAXN> del;
int ans=INT_MAX;
void dfssz(int u,int p=-1)
{
subsz[u]=1;
for(auto ch:g[u])
{
if(ch.first==p) continue;
if(!del.test(ch.first))
{
dfssz(ch.first,u);
subsz[u]+=subsz[ch.first];
}
}
}
int getcen(int u,int sz,int p=-1)
{
for(auto ch:g[u])
{
if(ch.first==p) continue;
if(!del.test(ch.first))
if(subsz[ch.first]>sz/2) return getcen(ch.first,sz,u);
}
return u;
}
void place(map<int,int> &m,map<int,int> &m2,int len,int nm,int K)
{
if(m2.find(len)==m2.end()) m2[len]=nm;
else m2[len]=min(m2[len],nm);
if(m.find(K-len)!=m.end()) ans=min(ans,m2[len]+m[K-len]);
}
void solve(int u,map<int,int> &m,map<int,int> &m2,int len,int K,int dep,int p)
{
for(auto ch:g[u])
{
if(ch.first==p) continue;
if(!del.test(ch.first))
if(len+ch.second<=K)
{
place(m,m2,len+ch.second,1+dep,K);
solve(ch.first,m,m2,len+ch.second,K,1+dep,u);
}
}
}
void centroid(int u,const int& K)
{
dfssz(u);
int C=getcen(u,subsz[u]);
map<int,int> m;
for(auto ch:g[C])
{
if(!del.test(ch.first))
if(ch.second<=K)
{
map<int,int> m2;
place(m,m2,ch.second,1,K);
solve(ch.first,m,m2,ch.second,K,1,C);
for(auto p:m2)
{
if(m.find(p.first)==m.end()) m[p.first]=p.second;
else m[p.first]=min(m[p.first],p.second);
}
}
}
if(m.find(K)!=m.end()) ans=min(ans,m[K]);
del.flip(C);
for(auto ch:g[C])
if(!del.test(ch.first)) centroid(ch.first,K);
}
int best_path(int N, int K, int H[][2], int L[])
{
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]);
}
centroid(0,K);
if(ans==INT_MAX) return -1;
else return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
5 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
4 ms |
5708 KB |
Output is correct |
6 |
Correct |
4 ms |
5708 KB |
Output is correct |
7 |
Correct |
4 ms |
5800 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
4 ms |
5708 KB |
Output is correct |
10 |
Correct |
4 ms |
5708 KB |
Output is correct |
11 |
Correct |
4 ms |
5708 KB |
Output is correct |
12 |
Correct |
4 ms |
5708 KB |
Output is correct |
13 |
Correct |
4 ms |
5708 KB |
Output is correct |
14 |
Correct |
4 ms |
5708 KB |
Output is correct |
15 |
Correct |
4 ms |
5708 KB |
Output is correct |
16 |
Correct |
4 ms |
5792 KB |
Output is correct |
17 |
Correct |
4 ms |
5708 KB |
Output is correct |
18 |
Correct |
4 ms |
5708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
5 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
4 ms |
5708 KB |
Output is correct |
6 |
Correct |
4 ms |
5708 KB |
Output is correct |
7 |
Correct |
4 ms |
5800 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
4 ms |
5708 KB |
Output is correct |
10 |
Correct |
4 ms |
5708 KB |
Output is correct |
11 |
Correct |
4 ms |
5708 KB |
Output is correct |
12 |
Correct |
4 ms |
5708 KB |
Output is correct |
13 |
Correct |
4 ms |
5708 KB |
Output is correct |
14 |
Correct |
4 ms |
5708 KB |
Output is correct |
15 |
Correct |
4 ms |
5708 KB |
Output is correct |
16 |
Correct |
4 ms |
5792 KB |
Output is correct |
17 |
Correct |
4 ms |
5708 KB |
Output is correct |
18 |
Correct |
4 ms |
5708 KB |
Output is correct |
19 |
Correct |
4 ms |
5708 KB |
Output is correct |
20 |
Correct |
5 ms |
5708 KB |
Output is correct |
21 |
Correct |
6 ms |
5872 KB |
Output is correct |
22 |
Correct |
6 ms |
5836 KB |
Output is correct |
23 |
Correct |
6 ms |
5836 KB |
Output is correct |
24 |
Correct |
6 ms |
5832 KB |
Output is correct |
25 |
Correct |
6 ms |
5836 KB |
Output is correct |
26 |
Correct |
5 ms |
5836 KB |
Output is correct |
27 |
Correct |
5 ms |
5780 KB |
Output is correct |
28 |
Correct |
6 ms |
5836 KB |
Output is correct |
29 |
Correct |
6 ms |
5836 KB |
Output is correct |
30 |
Correct |
6 ms |
5836 KB |
Output is correct |
31 |
Correct |
6 ms |
5836 KB |
Output is correct |
32 |
Correct |
6 ms |
5836 KB |
Output is correct |
33 |
Correct |
6 ms |
5816 KB |
Output is correct |
34 |
Correct |
5 ms |
5836 KB |
Output is correct |
35 |
Correct |
5 ms |
5836 KB |
Output is correct |
36 |
Correct |
5 ms |
5836 KB |
Output is correct |
37 |
Correct |
6 ms |
5836 KB |
Output is correct |
38 |
Correct |
6 ms |
5836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
5 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
4 ms |
5708 KB |
Output is correct |
6 |
Correct |
4 ms |
5708 KB |
Output is correct |
7 |
Correct |
4 ms |
5800 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
4 ms |
5708 KB |
Output is correct |
10 |
Correct |
4 ms |
5708 KB |
Output is correct |
11 |
Correct |
4 ms |
5708 KB |
Output is correct |
12 |
Correct |
4 ms |
5708 KB |
Output is correct |
13 |
Correct |
4 ms |
5708 KB |
Output is correct |
14 |
Correct |
4 ms |
5708 KB |
Output is correct |
15 |
Correct |
4 ms |
5708 KB |
Output is correct |
16 |
Correct |
4 ms |
5792 KB |
Output is correct |
17 |
Correct |
4 ms |
5708 KB |
Output is correct |
18 |
Correct |
4 ms |
5708 KB |
Output is correct |
19 |
Correct |
264 ms |
10584 KB |
Output is correct |
20 |
Correct |
258 ms |
10776 KB |
Output is correct |
21 |
Correct |
273 ms |
10692 KB |
Output is correct |
22 |
Correct |
257 ms |
10796 KB |
Output is correct |
23 |
Correct |
117 ms |
10888 KB |
Output is correct |
24 |
Correct |
107 ms |
10740 KB |
Output is correct |
25 |
Correct |
175 ms |
13400 KB |
Output is correct |
26 |
Correct |
123 ms |
16364 KB |
Output is correct |
27 |
Correct |
270 ms |
15828 KB |
Output is correct |
28 |
Correct |
345 ms |
26864 KB |
Output is correct |
29 |
Correct |
309 ms |
25976 KB |
Output is correct |
30 |
Correct |
286 ms |
15600 KB |
Output is correct |
31 |
Correct |
271 ms |
15708 KB |
Output is correct |
32 |
Correct |
287 ms |
15820 KB |
Output is correct |
33 |
Correct |
476 ms |
14600 KB |
Output is correct |
34 |
Correct |
214 ms |
14512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
5 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
4 ms |
5708 KB |
Output is correct |
6 |
Correct |
4 ms |
5708 KB |
Output is correct |
7 |
Correct |
4 ms |
5800 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
4 ms |
5708 KB |
Output is correct |
10 |
Correct |
4 ms |
5708 KB |
Output is correct |
11 |
Correct |
4 ms |
5708 KB |
Output is correct |
12 |
Correct |
4 ms |
5708 KB |
Output is correct |
13 |
Correct |
4 ms |
5708 KB |
Output is correct |
14 |
Correct |
4 ms |
5708 KB |
Output is correct |
15 |
Correct |
4 ms |
5708 KB |
Output is correct |
16 |
Correct |
4 ms |
5792 KB |
Output is correct |
17 |
Correct |
4 ms |
5708 KB |
Output is correct |
18 |
Correct |
4 ms |
5708 KB |
Output is correct |
19 |
Correct |
4 ms |
5708 KB |
Output is correct |
20 |
Correct |
5 ms |
5708 KB |
Output is correct |
21 |
Correct |
6 ms |
5872 KB |
Output is correct |
22 |
Correct |
6 ms |
5836 KB |
Output is correct |
23 |
Correct |
6 ms |
5836 KB |
Output is correct |
24 |
Correct |
6 ms |
5832 KB |
Output is correct |
25 |
Correct |
6 ms |
5836 KB |
Output is correct |
26 |
Correct |
5 ms |
5836 KB |
Output is correct |
27 |
Correct |
5 ms |
5780 KB |
Output is correct |
28 |
Correct |
6 ms |
5836 KB |
Output is correct |
29 |
Correct |
6 ms |
5836 KB |
Output is correct |
30 |
Correct |
6 ms |
5836 KB |
Output is correct |
31 |
Correct |
6 ms |
5836 KB |
Output is correct |
32 |
Correct |
6 ms |
5836 KB |
Output is correct |
33 |
Correct |
6 ms |
5816 KB |
Output is correct |
34 |
Correct |
5 ms |
5836 KB |
Output is correct |
35 |
Correct |
5 ms |
5836 KB |
Output is correct |
36 |
Correct |
5 ms |
5836 KB |
Output is correct |
37 |
Correct |
6 ms |
5836 KB |
Output is correct |
38 |
Correct |
6 ms |
5836 KB |
Output is correct |
39 |
Correct |
264 ms |
10584 KB |
Output is correct |
40 |
Correct |
258 ms |
10776 KB |
Output is correct |
41 |
Correct |
273 ms |
10692 KB |
Output is correct |
42 |
Correct |
257 ms |
10796 KB |
Output is correct |
43 |
Correct |
117 ms |
10888 KB |
Output is correct |
44 |
Correct |
107 ms |
10740 KB |
Output is correct |
45 |
Correct |
175 ms |
13400 KB |
Output is correct |
46 |
Correct |
123 ms |
16364 KB |
Output is correct |
47 |
Correct |
270 ms |
15828 KB |
Output is correct |
48 |
Correct |
345 ms |
26864 KB |
Output is correct |
49 |
Correct |
309 ms |
25976 KB |
Output is correct |
50 |
Correct |
286 ms |
15600 KB |
Output is correct |
51 |
Correct |
271 ms |
15708 KB |
Output is correct |
52 |
Correct |
287 ms |
15820 KB |
Output is correct |
53 |
Correct |
476 ms |
14600 KB |
Output is correct |
54 |
Correct |
214 ms |
14512 KB |
Output is correct |
55 |
Correct |
34 ms |
6636 KB |
Output is correct |
56 |
Correct |
21 ms |
6348 KB |
Output is correct |
57 |
Correct |
185 ms |
10896 KB |
Output is correct |
58 |
Correct |
58 ms |
10800 KB |
Output is correct |
59 |
Correct |
542 ms |
23316 KB |
Output is correct |
60 |
Correct |
1431 ms |
43460 KB |
Output is correct |
61 |
Correct |
384 ms |
15956 KB |
Output is correct |
62 |
Correct |
430 ms |
15880 KB |
Output is correct |
63 |
Correct |
498 ms |
15812 KB |
Output is correct |
64 |
Correct |
1401 ms |
26588 KB |
Output is correct |
65 |
Correct |
267 ms |
15556 KB |
Output is correct |
66 |
Correct |
925 ms |
25344 KB |
Output is correct |
67 |
Correct |
156 ms |
15924 KB |
Output is correct |
68 |
Correct |
616 ms |
22768 KB |
Output is correct |
69 |
Correct |
544 ms |
23048 KB |
Output is correct |
70 |
Correct |
519 ms |
22196 KB |
Output is correct |