#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define in insert
#define F first
#define S second
vector<int> adj[200009];
int par1[200009],par[200009][21],depth[200009],cnt[200009],nxt=0,good[200009],val[2000009];
int get_par(int node){
if(par1[node]==node) return node;
return par1[node]=get_par(par1[node]);
}
void merg(int u, int v ,int w){
int uu=get_par(u);
int vv=get_par(v);
nxt++;
val[nxt]=w;
if(uu==vv){
adj[nxt].pb(uu);
cnt[u]++;
cnt[v]++;
good[nxt]=1;
par1[uu]=nxt;
return ;
}
adj[nxt].pb(uu);
adj[nxt].pb(vv);
cnt[u]++;
cnt[v]++;
par1[uu]=nxt;
par1[vv]=nxt;
if(cnt[u]>=3 || cnt[v]>=3) good[nxt]=1;
return ;
}
void dfs(int node , int p){
par[node][0]=p;
for(int i=1;i<=20;i++) par[node][i]=par[par[node][i-1]][i-1];
for(auto u : adj[node]){
depth[u]=1+depth[node];
dfs(u,node);
good[node]|=good[u];
}
//cout<<" # "<<node<<' '<<good[node]<<' '<<val[node]<<endl;
return ;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
nxt=N-1;
for(int i=0;i<N+M;i++) par1[i]=i;
vector<pair<int,pair<int,int>>> v;
for(int i=0;i<M;i++){
v.pb({W[i],{U[i],V[i]}});
}
sort(v.begin(),v.end());
for(auto u : v){
merg(u.S.F,u.S.S,u.F);
}
dfs(nxt,nxt);
return ;
}
int lca(int u , int v){
if(depth[v]>depth[u]) swap(u,v);
for(int i=20;i>=0;i--) if(depth[u]-(1<<i)>=depth[v]) u=par[u][i];
if(u==v) return u;
for(int i=20;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
return par[u][0];
}
int getMinimumFuelCapacity(int X, int Y) {
int lc=lca(X,Y);
//cout<<" @ "<<X<<' '<<Y<<' '<<lc<<endl;
if(good[lc]==1) return val[lc];
for(int i=20;i>=0;i--) if(good[par[lc][i]]==0) lc=par[lc][i];
lc=par[lc][0];
if(good[lc]) return val[lc];
return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
9816 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
3 ms |
9564 KB |
Output is correct |
4 |
Correct |
2 ms |
9820 KB |
Output is correct |
5 |
Correct |
3 ms |
9820 KB |
Output is correct |
6 |
Correct |
2 ms |
9820 KB |
Output is correct |
7 |
Correct |
2 ms |
9820 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
73 ms |
31696 KB |
Output is correct |
10 |
Correct |
96 ms |
34760 KB |
Output is correct |
11 |
Correct |
89 ms |
34668 KB |
Output is correct |
12 |
Correct |
102 ms |
34984 KB |
Output is correct |
13 |
Correct |
81 ms |
38836 KB |
Output is correct |
14 |
Correct |
84 ms |
33460 KB |
Output is correct |
15 |
Correct |
207 ms |
38596 KB |
Output is correct |
16 |
Correct |
196 ms |
38264 KB |
Output is correct |
17 |
Correct |
211 ms |
38948 KB |
Output is correct |
18 |
Correct |
256 ms |
42800 KB |
Output is correct |
19 |
Correct |
85 ms |
22356 KB |
Output is correct |
20 |
Correct |
218 ms |
38568 KB |
Output is correct |
21 |
Correct |
224 ms |
38964 KB |
Output is correct |
22 |
Correct |
211 ms |
39312 KB |
Output is correct |
23 |
Correct |
239 ms |
43140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
9816 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
175 ms |
43756 KB |
Output is correct |
4 |
Correct |
183 ms |
48016 KB |
Output is correct |
5 |
Correct |
217 ms |
48108 KB |
Output is correct |
6 |
Correct |
179 ms |
48040 KB |
Output is correct |
7 |
Correct |
189 ms |
48060 KB |
Output is correct |
8 |
Correct |
199 ms |
47652 KB |
Output is correct |
9 |
Correct |
175 ms |
47952 KB |
Output is correct |
10 |
Correct |
175 ms |
47416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
9816 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
3 ms |
9564 KB |
Output is correct |
4 |
Correct |
2 ms |
9820 KB |
Output is correct |
5 |
Correct |
3 ms |
9820 KB |
Output is correct |
6 |
Correct |
2 ms |
9820 KB |
Output is correct |
7 |
Correct |
2 ms |
9820 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
2 ms |
11612 KB |
Output is correct |
10 |
Correct |
3 ms |
11868 KB |
Output is correct |
11 |
Correct |
3 ms |
11868 KB |
Output is correct |
12 |
Correct |
3 ms |
11868 KB |
Output is correct |
13 |
Correct |
3 ms |
11868 KB |
Output is correct |
14 |
Correct |
3 ms |
11868 KB |
Output is correct |
15 |
Correct |
3 ms |
11868 KB |
Output is correct |
16 |
Correct |
3 ms |
11868 KB |
Output is correct |
17 |
Correct |
3 ms |
11868 KB |
Output is correct |
18 |
Correct |
3 ms |
12120 KB |
Output is correct |
19 |
Correct |
3 ms |
11864 KB |
Output is correct |
20 |
Correct |
3 ms |
11868 KB |
Output is correct |
21 |
Correct |
3 ms |
11868 KB |
Output is correct |
22 |
Correct |
3 ms |
11924 KB |
Output is correct |
23 |
Correct |
3 ms |
11868 KB |
Output is correct |
24 |
Correct |
3 ms |
11868 KB |
Output is correct |
25 |
Correct |
3 ms |
11868 KB |
Output is correct |
26 |
Correct |
3 ms |
11868 KB |
Output is correct |
27 |
Correct |
3 ms |
11868 KB |
Output is correct |
28 |
Correct |
3 ms |
11868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
11612 KB |
Output is correct |
2 |
Correct |
3 ms |
9816 KB |
Output is correct |
3 |
Correct |
2 ms |
9564 KB |
Output is correct |
4 |
Correct |
3 ms |
9564 KB |
Output is correct |
5 |
Correct |
2 ms |
9820 KB |
Output is correct |
6 |
Correct |
3 ms |
9820 KB |
Output is correct |
7 |
Correct |
2 ms |
9820 KB |
Output is correct |
8 |
Correct |
2 ms |
9820 KB |
Output is correct |
9 |
Correct |
3 ms |
9820 KB |
Output is correct |
10 |
Correct |
73 ms |
31696 KB |
Output is correct |
11 |
Correct |
96 ms |
34760 KB |
Output is correct |
12 |
Correct |
89 ms |
34668 KB |
Output is correct |
13 |
Correct |
102 ms |
34984 KB |
Output is correct |
14 |
Correct |
81 ms |
38836 KB |
Output is correct |
15 |
Correct |
3 ms |
11868 KB |
Output is correct |
16 |
Correct |
3 ms |
11868 KB |
Output is correct |
17 |
Correct |
3 ms |
11868 KB |
Output is correct |
18 |
Correct |
3 ms |
11868 KB |
Output is correct |
19 |
Correct |
3 ms |
11868 KB |
Output is correct |
20 |
Correct |
3 ms |
11868 KB |
Output is correct |
21 |
Correct |
3 ms |
11868 KB |
Output is correct |
22 |
Correct |
3 ms |
11868 KB |
Output is correct |
23 |
Correct |
3 ms |
12120 KB |
Output is correct |
24 |
Correct |
3 ms |
11864 KB |
Output is correct |
25 |
Correct |
3 ms |
11868 KB |
Output is correct |
26 |
Correct |
3 ms |
11868 KB |
Output is correct |
27 |
Correct |
3 ms |
11924 KB |
Output is correct |
28 |
Correct |
3 ms |
11868 KB |
Output is correct |
29 |
Correct |
3 ms |
11868 KB |
Output is correct |
30 |
Correct |
3 ms |
11868 KB |
Output is correct |
31 |
Correct |
3 ms |
11868 KB |
Output is correct |
32 |
Correct |
3 ms |
11868 KB |
Output is correct |
33 |
Correct |
3 ms |
11868 KB |
Output is correct |
34 |
Correct |
11 ms |
15128 KB |
Output is correct |
35 |
Correct |
117 ms |
36552 KB |
Output is correct |
36 |
Correct |
100 ms |
36528 KB |
Output is correct |
37 |
Correct |
101 ms |
36528 KB |
Output is correct |
38 |
Correct |
103 ms |
36392 KB |
Output is correct |
39 |
Correct |
107 ms |
36552 KB |
Output is correct |
40 |
Correct |
87 ms |
35780 KB |
Output is correct |
41 |
Correct |
101 ms |
35012 KB |
Output is correct |
42 |
Correct |
100 ms |
34756 KB |
Output is correct |
43 |
Correct |
84 ms |
41672 KB |
Output is correct |
44 |
Correct |
100 ms |
36916 KB |
Output is correct |
45 |
Runtime error |
107 ms |
50356 KB |
Execution killed with signal 11 |
46 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
9816 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
3 ms |
9564 KB |
Output is correct |
4 |
Correct |
2 ms |
9820 KB |
Output is correct |
5 |
Correct |
3 ms |
9820 KB |
Output is correct |
6 |
Correct |
2 ms |
9820 KB |
Output is correct |
7 |
Correct |
2 ms |
9820 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
73 ms |
31696 KB |
Output is correct |
10 |
Correct |
96 ms |
34760 KB |
Output is correct |
11 |
Correct |
89 ms |
34668 KB |
Output is correct |
12 |
Correct |
102 ms |
34984 KB |
Output is correct |
13 |
Correct |
81 ms |
38836 KB |
Output is correct |
14 |
Correct |
84 ms |
33460 KB |
Output is correct |
15 |
Correct |
207 ms |
38596 KB |
Output is correct |
16 |
Correct |
196 ms |
38264 KB |
Output is correct |
17 |
Correct |
211 ms |
38948 KB |
Output is correct |
18 |
Correct |
256 ms |
42800 KB |
Output is correct |
19 |
Correct |
175 ms |
43756 KB |
Output is correct |
20 |
Correct |
183 ms |
48016 KB |
Output is correct |
21 |
Correct |
217 ms |
48108 KB |
Output is correct |
22 |
Correct |
179 ms |
48040 KB |
Output is correct |
23 |
Correct |
189 ms |
48060 KB |
Output is correct |
24 |
Correct |
199 ms |
47652 KB |
Output is correct |
25 |
Correct |
175 ms |
47952 KB |
Output is correct |
26 |
Correct |
175 ms |
47416 KB |
Output is correct |
27 |
Correct |
3 ms |
11868 KB |
Output is correct |
28 |
Correct |
3 ms |
11868 KB |
Output is correct |
29 |
Correct |
3 ms |
11868 KB |
Output is correct |
30 |
Correct |
3 ms |
11868 KB |
Output is correct |
31 |
Correct |
3 ms |
11868 KB |
Output is correct |
32 |
Correct |
3 ms |
11868 KB |
Output is correct |
33 |
Correct |
3 ms |
11868 KB |
Output is correct |
34 |
Correct |
3 ms |
11868 KB |
Output is correct |
35 |
Correct |
3 ms |
12120 KB |
Output is correct |
36 |
Correct |
11 ms |
15128 KB |
Output is correct |
37 |
Correct |
117 ms |
36552 KB |
Output is correct |
38 |
Correct |
100 ms |
36528 KB |
Output is correct |
39 |
Correct |
101 ms |
36528 KB |
Output is correct |
40 |
Correct |
103 ms |
36392 KB |
Output is correct |
41 |
Correct |
107 ms |
36552 KB |
Output is correct |
42 |
Correct |
87 ms |
35780 KB |
Output is correct |
43 |
Correct |
101 ms |
35012 KB |
Output is correct |
44 |
Correct |
100 ms |
34756 KB |
Output is correct |
45 |
Correct |
84 ms |
41672 KB |
Output is correct |
46 |
Correct |
100 ms |
36916 KB |
Output is correct |
47 |
Correct |
18 ms |
15240 KB |
Output is correct |
48 |
Correct |
197 ms |
40388 KB |
Output is correct |
49 |
Correct |
191 ms |
40516 KB |
Output is correct |
50 |
Correct |
211 ms |
40652 KB |
Output is correct |
51 |
Correct |
221 ms |
40392 KB |
Output is correct |
52 |
Correct |
218 ms |
40012 KB |
Output is correct |
53 |
Correct |
162 ms |
36912 KB |
Output is correct |
54 |
Correct |
233 ms |
39316 KB |
Output is correct |
55 |
Correct |
247 ms |
38548 KB |
Output is correct |
56 |
Correct |
278 ms |
44488 KB |
Output is correct |
57 |
Correct |
226 ms |
41344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
11612 KB |
Output is correct |
2 |
Correct |
3 ms |
9816 KB |
Output is correct |
3 |
Correct |
2 ms |
9564 KB |
Output is correct |
4 |
Correct |
3 ms |
9564 KB |
Output is correct |
5 |
Correct |
2 ms |
9820 KB |
Output is correct |
6 |
Correct |
3 ms |
9820 KB |
Output is correct |
7 |
Correct |
2 ms |
9820 KB |
Output is correct |
8 |
Correct |
2 ms |
9820 KB |
Output is correct |
9 |
Correct |
3 ms |
9820 KB |
Output is correct |
10 |
Correct |
73 ms |
31696 KB |
Output is correct |
11 |
Correct |
96 ms |
34760 KB |
Output is correct |
12 |
Correct |
89 ms |
34668 KB |
Output is correct |
13 |
Correct |
102 ms |
34984 KB |
Output is correct |
14 |
Correct |
81 ms |
38836 KB |
Output is correct |
15 |
Correct |
84 ms |
33460 KB |
Output is correct |
16 |
Correct |
207 ms |
38596 KB |
Output is correct |
17 |
Correct |
196 ms |
38264 KB |
Output is correct |
18 |
Correct |
211 ms |
38948 KB |
Output is correct |
19 |
Correct |
256 ms |
42800 KB |
Output is correct |
20 |
Correct |
175 ms |
43756 KB |
Output is correct |
21 |
Correct |
183 ms |
48016 KB |
Output is correct |
22 |
Correct |
217 ms |
48108 KB |
Output is correct |
23 |
Correct |
179 ms |
48040 KB |
Output is correct |
24 |
Correct |
189 ms |
48060 KB |
Output is correct |
25 |
Correct |
199 ms |
47652 KB |
Output is correct |
26 |
Correct |
175 ms |
47952 KB |
Output is correct |
27 |
Correct |
175 ms |
47416 KB |
Output is correct |
28 |
Correct |
3 ms |
11868 KB |
Output is correct |
29 |
Correct |
3 ms |
11868 KB |
Output is correct |
30 |
Correct |
3 ms |
11868 KB |
Output is correct |
31 |
Correct |
3 ms |
11868 KB |
Output is correct |
32 |
Correct |
3 ms |
11868 KB |
Output is correct |
33 |
Correct |
3 ms |
11868 KB |
Output is correct |
34 |
Correct |
3 ms |
11868 KB |
Output is correct |
35 |
Correct |
3 ms |
11868 KB |
Output is correct |
36 |
Correct |
3 ms |
12120 KB |
Output is correct |
37 |
Correct |
11 ms |
15128 KB |
Output is correct |
38 |
Correct |
117 ms |
36552 KB |
Output is correct |
39 |
Correct |
100 ms |
36528 KB |
Output is correct |
40 |
Correct |
101 ms |
36528 KB |
Output is correct |
41 |
Correct |
103 ms |
36392 KB |
Output is correct |
42 |
Correct |
107 ms |
36552 KB |
Output is correct |
43 |
Correct |
87 ms |
35780 KB |
Output is correct |
44 |
Correct |
101 ms |
35012 KB |
Output is correct |
45 |
Correct |
100 ms |
34756 KB |
Output is correct |
46 |
Correct |
84 ms |
41672 KB |
Output is correct |
47 |
Correct |
100 ms |
36916 KB |
Output is correct |
48 |
Correct |
18 ms |
15240 KB |
Output is correct |
49 |
Correct |
197 ms |
40388 KB |
Output is correct |
50 |
Correct |
191 ms |
40516 KB |
Output is correct |
51 |
Correct |
211 ms |
40652 KB |
Output is correct |
52 |
Correct |
221 ms |
40392 KB |
Output is correct |
53 |
Correct |
218 ms |
40012 KB |
Output is correct |
54 |
Correct |
162 ms |
36912 KB |
Output is correct |
55 |
Correct |
233 ms |
39316 KB |
Output is correct |
56 |
Correct |
247 ms |
38548 KB |
Output is correct |
57 |
Correct |
278 ms |
44488 KB |
Output is correct |
58 |
Correct |
226 ms |
41344 KB |
Output is correct |
59 |
Correct |
85 ms |
22356 KB |
Output is correct |
60 |
Correct |
218 ms |
38568 KB |
Output is correct |
61 |
Correct |
224 ms |
38964 KB |
Output is correct |
62 |
Correct |
211 ms |
39312 KB |
Output is correct |
63 |
Correct |
239 ms |
43140 KB |
Output is correct |
64 |
Correct |
3 ms |
11864 KB |
Output is correct |
65 |
Correct |
3 ms |
11868 KB |
Output is correct |
66 |
Correct |
3 ms |
11868 KB |
Output is correct |
67 |
Correct |
3 ms |
11924 KB |
Output is correct |
68 |
Correct |
3 ms |
11868 KB |
Output is correct |
69 |
Correct |
3 ms |
11868 KB |
Output is correct |
70 |
Correct |
3 ms |
11868 KB |
Output is correct |
71 |
Correct |
3 ms |
11868 KB |
Output is correct |
72 |
Correct |
3 ms |
11868 KB |
Output is correct |
73 |
Correct |
3 ms |
11868 KB |
Output is correct |
74 |
Runtime error |
107 ms |
50356 KB |
Execution killed with signal 11 |
75 |
Halted |
0 ms |
0 KB |
- |