#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int lg = 20;
int n, m, gr[maxn], ds[maxn], dsz[maxn], mn[maxn];
vector<int> mn0[maxn];
vector<pair<int,pair<int,int>>> edgs;
int p[maxn][lg+2], w[maxn][lg+2], h[maxn];
vector<pair<int,int>> g[maxn];
int find(int u) {
if(ds[u] == u) return u;
return ds[u] = find(ds[u]);
}
void join(int u, int v, int id) {
gr[u]++;
gr[v]++;
int mxgr = max(gr[u],gr[v]);
u = find(u);
v = find(v);
if(u == v || mxgr >= 3 || mn[u] != -1 || mn[v] != -1) {
if(mn0[u].size()) {
for(auto x : mn0[u]) {
mn[x] = id;
}
mn0[u].clear();
}
if(mn0[v].size()) {
for(auto x : mn0[v]) {
mn[x] = id;
}
mn0[v].clear();
}
}
if(u == v) return;
if(dsz[u] < dsz[v]) swap(u,v);
for(auto x : mn0[v]) {
mn0[u].pb(x);
}
dsz[u]+= dsz[v];
ds[v] = u;
}
int ds1[maxn], dsz1[maxn];
int find1(int u) {
if(ds1[u] == u) return u;
return ds1[u] = find1(ds1[u]);
}
void join1(int u, int v) {
u = find1(u);
v = find1(v);
if(u == v) return;
if(dsz1[u] < dsz1[v]) swap(u,v);
dsz1[u]+= dsz1[v];
ds1[v] = u;
}
void dfs(int u, int ant, int antw) {
p[u][0] = ant;
w[u][0] = antw;
for(int i = 1; i <= lg; i++) {
p[u][i] = p[p[u][i-1]][i-1];
w[u][i] = max(w[u][i-1],w[p[u][i-1]][i-1]);
}
for(auto V : g[u]) if(V.fr != ant) {
h[V.fr] = h[u]+1;
dfs(V.fr,u,V.sc);
}
}
int lca(int u, int v) {
int ans = 0;
if(h[u] < h[v]) swap(u,v);
for(int i = lg; i >= 0; i--) {
if(h[p[u][i]] >= h[v]) {
ans = max(ans, w[u][i]);
u = p[u][i];
}
}
if(u == v) return ans;
for(int i = lg; i >= 0; i--) {
if(p[u][i] != p[v][i]) {
ans = max(ans,w[u][i]);
u = p[u][i];
ans = max(ans,w[v][i]);
v = p[v][i];
}
}
ans = max(ans, w[u][0]);
ans = max(ans, w[v][0]);
return ans;
}
void init(int N, int M, vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
for(auto i = 0; i < m; i++) {
edgs.pb(mp(W[i],mp(U[i],V[i])));
}
sort(all(edgs));
for(int i = 0; i < n; i++) {
gr[i] = 0;
mn[i] = -1;
ds[i] = i;
dsz[i] = 1;
mn0[i].clear();
mn0[i].pb(i);
p[i][0] = -1;
}
for(int i = 0; i < m; i++) {
int u = edgs[i].sc.fr;
int v = edgs[i].sc.sc;
if(find(u) != find(v)) {
g[u].pb(mp(v,i));
g[v].pb(mp(u,i));
}
join(u,v,i);
}
dfs(0,0,-1);
}
int getMinimumFuelCapacity(int x, int y) {
if(mn[x] == -1 || mn[y] == -1) return -1;
return edgs[max({lca(x,y),mn[x],mn[y]})].fr;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9812 KB |
Output is correct |
5 |
Correct |
6 ms |
9940 KB |
Output is correct |
6 |
Correct |
5 ms |
10020 KB |
Output is correct |
7 |
Correct |
5 ms |
10068 KB |
Output is correct |
8 |
Correct |
5 ms |
10068 KB |
Output is correct |
9 |
Correct |
133 ms |
38648 KB |
Output is correct |
10 |
Correct |
176 ms |
45504 KB |
Output is correct |
11 |
Correct |
169 ms |
44612 KB |
Output is correct |
12 |
Correct |
185 ms |
47004 KB |
Output is correct |
13 |
Correct |
164 ms |
45824 KB |
Output is correct |
14 |
Correct |
151 ms |
37972 KB |
Output is correct |
15 |
Correct |
232 ms |
47736 KB |
Output is correct |
16 |
Correct |
227 ms |
45288 KB |
Output is correct |
17 |
Correct |
245 ms |
50264 KB |
Output is correct |
18 |
Correct |
207 ms |
46328 KB |
Output is correct |
19 |
Correct |
101 ms |
19104 KB |
Output is correct |
20 |
Correct |
401 ms |
48280 KB |
Output is correct |
21 |
Correct |
414 ms |
46528 KB |
Output is correct |
22 |
Correct |
443 ms |
49880 KB |
Output is correct |
23 |
Correct |
377 ms |
47396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
219 ms |
40892 KB |
Output is correct |
4 |
Correct |
212 ms |
42252 KB |
Output is correct |
5 |
Correct |
206 ms |
41452 KB |
Output is correct |
6 |
Correct |
216 ms |
42096 KB |
Output is correct |
7 |
Correct |
214 ms |
41920 KB |
Output is correct |
8 |
Correct |
200 ms |
40656 KB |
Output is correct |
9 |
Correct |
204 ms |
41844 KB |
Output is correct |
10 |
Correct |
211 ms |
40428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9812 KB |
Output is correct |
5 |
Correct |
6 ms |
9940 KB |
Output is correct |
6 |
Correct |
5 ms |
10020 KB |
Output is correct |
7 |
Correct |
5 ms |
10068 KB |
Output is correct |
8 |
Correct |
5 ms |
10068 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
8 ms |
10004 KB |
Output is correct |
11 |
Correct |
6 ms |
10068 KB |
Output is correct |
12 |
Correct |
6 ms |
10000 KB |
Output is correct |
13 |
Correct |
6 ms |
9940 KB |
Output is correct |
14 |
Correct |
6 ms |
9940 KB |
Output is correct |
15 |
Correct |
6 ms |
9980 KB |
Output is correct |
16 |
Correct |
6 ms |
10068 KB |
Output is correct |
17 |
Correct |
6 ms |
10068 KB |
Output is correct |
18 |
Correct |
6 ms |
10024 KB |
Output is correct |
19 |
Correct |
6 ms |
9940 KB |
Output is correct |
20 |
Correct |
6 ms |
10048 KB |
Output is correct |
21 |
Correct |
6 ms |
9940 KB |
Output is correct |
22 |
Correct |
6 ms |
9812 KB |
Output is correct |
23 |
Correct |
6 ms |
9892 KB |
Output is correct |
24 |
Correct |
7 ms |
10068 KB |
Output is correct |
25 |
Correct |
6 ms |
10068 KB |
Output is correct |
26 |
Correct |
7 ms |
10068 KB |
Output is correct |
27 |
Correct |
6 ms |
10028 KB |
Output is correct |
28 |
Correct |
6 ms |
9956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9812 KB |
Output is correct |
6 |
Correct |
6 ms |
9940 KB |
Output is correct |
7 |
Correct |
5 ms |
10020 KB |
Output is correct |
8 |
Correct |
5 ms |
10068 KB |
Output is correct |
9 |
Correct |
5 ms |
10068 KB |
Output is correct |
10 |
Correct |
133 ms |
38648 KB |
Output is correct |
11 |
Correct |
176 ms |
45504 KB |
Output is correct |
12 |
Correct |
169 ms |
44612 KB |
Output is correct |
13 |
Correct |
185 ms |
47004 KB |
Output is correct |
14 |
Correct |
164 ms |
45824 KB |
Output is correct |
15 |
Correct |
8 ms |
10004 KB |
Output is correct |
16 |
Correct |
6 ms |
10068 KB |
Output is correct |
17 |
Correct |
6 ms |
10000 KB |
Output is correct |
18 |
Correct |
6 ms |
9940 KB |
Output is correct |
19 |
Correct |
6 ms |
9940 KB |
Output is correct |
20 |
Correct |
6 ms |
9980 KB |
Output is correct |
21 |
Correct |
6 ms |
10068 KB |
Output is correct |
22 |
Correct |
6 ms |
10068 KB |
Output is correct |
23 |
Correct |
6 ms |
10024 KB |
Output is correct |
24 |
Correct |
6 ms |
9940 KB |
Output is correct |
25 |
Correct |
6 ms |
10048 KB |
Output is correct |
26 |
Correct |
6 ms |
9940 KB |
Output is correct |
27 |
Correct |
6 ms |
9812 KB |
Output is correct |
28 |
Correct |
6 ms |
9892 KB |
Output is correct |
29 |
Correct |
7 ms |
10068 KB |
Output is correct |
30 |
Correct |
6 ms |
10068 KB |
Output is correct |
31 |
Correct |
7 ms |
10068 KB |
Output is correct |
32 |
Correct |
6 ms |
10028 KB |
Output is correct |
33 |
Correct |
6 ms |
9956 KB |
Output is correct |
34 |
Correct |
18 ms |
13704 KB |
Output is correct |
35 |
Correct |
189 ms |
45692 KB |
Output is correct |
36 |
Correct |
176 ms |
43116 KB |
Output is correct |
37 |
Correct |
161 ms |
40764 KB |
Output is correct |
38 |
Correct |
152 ms |
39456 KB |
Output is correct |
39 |
Correct |
144 ms |
38544 KB |
Output is correct |
40 |
Correct |
141 ms |
36160 KB |
Output is correct |
41 |
Correct |
191 ms |
44672 KB |
Output is correct |
42 |
Correct |
183 ms |
45760 KB |
Output is correct |
43 |
Correct |
147 ms |
43492 KB |
Output is correct |
44 |
Correct |
139 ms |
39288 KB |
Output is correct |
45 |
Correct |
131 ms |
35276 KB |
Output is correct |
46 |
Correct |
172 ms |
42332 KB |
Output is correct |
47 |
Correct |
148 ms |
39388 KB |
Output is correct |
48 |
Correct |
141 ms |
38652 KB |
Output is correct |
49 |
Correct |
62 ms |
16560 KB |
Output is correct |
50 |
Correct |
52 ms |
15860 KB |
Output is correct |
51 |
Correct |
119 ms |
30832 KB |
Output is correct |
52 |
Correct |
209 ms |
44628 KB |
Output is correct |
53 |
Correct |
187 ms |
42512 KB |
Output is correct |
54 |
Correct |
221 ms |
48140 KB |
Output is correct |
55 |
Correct |
159 ms |
44648 KB |
Output is correct |
56 |
Correct |
164 ms |
41676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9812 KB |
Output is correct |
5 |
Correct |
6 ms |
9940 KB |
Output is correct |
6 |
Correct |
5 ms |
10020 KB |
Output is correct |
7 |
Correct |
5 ms |
10068 KB |
Output is correct |
8 |
Correct |
5 ms |
10068 KB |
Output is correct |
9 |
Correct |
133 ms |
38648 KB |
Output is correct |
10 |
Correct |
176 ms |
45504 KB |
Output is correct |
11 |
Correct |
169 ms |
44612 KB |
Output is correct |
12 |
Correct |
185 ms |
47004 KB |
Output is correct |
13 |
Correct |
164 ms |
45824 KB |
Output is correct |
14 |
Correct |
151 ms |
37972 KB |
Output is correct |
15 |
Correct |
232 ms |
47736 KB |
Output is correct |
16 |
Correct |
227 ms |
45288 KB |
Output is correct |
17 |
Correct |
245 ms |
50264 KB |
Output is correct |
18 |
Correct |
207 ms |
46328 KB |
Output is correct |
19 |
Correct |
219 ms |
40892 KB |
Output is correct |
20 |
Correct |
212 ms |
42252 KB |
Output is correct |
21 |
Correct |
206 ms |
41452 KB |
Output is correct |
22 |
Correct |
216 ms |
42096 KB |
Output is correct |
23 |
Correct |
214 ms |
41920 KB |
Output is correct |
24 |
Correct |
200 ms |
40656 KB |
Output is correct |
25 |
Correct |
204 ms |
41844 KB |
Output is correct |
26 |
Correct |
211 ms |
40428 KB |
Output is correct |
27 |
Correct |
8 ms |
10004 KB |
Output is correct |
28 |
Correct |
6 ms |
10068 KB |
Output is correct |
29 |
Correct |
6 ms |
10000 KB |
Output is correct |
30 |
Correct |
6 ms |
9940 KB |
Output is correct |
31 |
Correct |
6 ms |
9940 KB |
Output is correct |
32 |
Correct |
6 ms |
9980 KB |
Output is correct |
33 |
Correct |
6 ms |
10068 KB |
Output is correct |
34 |
Correct |
6 ms |
10068 KB |
Output is correct |
35 |
Correct |
6 ms |
10024 KB |
Output is correct |
36 |
Correct |
18 ms |
13704 KB |
Output is correct |
37 |
Correct |
189 ms |
45692 KB |
Output is correct |
38 |
Correct |
176 ms |
43116 KB |
Output is correct |
39 |
Correct |
161 ms |
40764 KB |
Output is correct |
40 |
Correct |
152 ms |
39456 KB |
Output is correct |
41 |
Correct |
144 ms |
38544 KB |
Output is correct |
42 |
Correct |
141 ms |
36160 KB |
Output is correct |
43 |
Correct |
191 ms |
44672 KB |
Output is correct |
44 |
Correct |
183 ms |
45760 KB |
Output is correct |
45 |
Correct |
147 ms |
43492 KB |
Output is correct |
46 |
Correct |
139 ms |
39288 KB |
Output is correct |
47 |
Correct |
26 ms |
14112 KB |
Output is correct |
48 |
Correct |
442 ms |
51080 KB |
Output is correct |
49 |
Correct |
413 ms |
48776 KB |
Output is correct |
50 |
Correct |
376 ms |
47512 KB |
Output is correct |
51 |
Correct |
365 ms |
46512 KB |
Output is correct |
52 |
Correct |
319 ms |
43892 KB |
Output is correct |
53 |
Correct |
213 ms |
36460 KB |
Output is correct |
54 |
Correct |
435 ms |
51676 KB |
Output is correct |
55 |
Correct |
431 ms |
52136 KB |
Output is correct |
56 |
Correct |
376 ms |
50656 KB |
Output is correct |
57 |
Correct |
300 ms |
46848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9812 KB |
Output is correct |
6 |
Correct |
6 ms |
9940 KB |
Output is correct |
7 |
Correct |
5 ms |
10020 KB |
Output is correct |
8 |
Correct |
5 ms |
10068 KB |
Output is correct |
9 |
Correct |
5 ms |
10068 KB |
Output is correct |
10 |
Correct |
133 ms |
38648 KB |
Output is correct |
11 |
Correct |
176 ms |
45504 KB |
Output is correct |
12 |
Correct |
169 ms |
44612 KB |
Output is correct |
13 |
Correct |
185 ms |
47004 KB |
Output is correct |
14 |
Correct |
164 ms |
45824 KB |
Output is correct |
15 |
Correct |
151 ms |
37972 KB |
Output is correct |
16 |
Correct |
232 ms |
47736 KB |
Output is correct |
17 |
Correct |
227 ms |
45288 KB |
Output is correct |
18 |
Correct |
245 ms |
50264 KB |
Output is correct |
19 |
Correct |
207 ms |
46328 KB |
Output is correct |
20 |
Correct |
219 ms |
40892 KB |
Output is correct |
21 |
Correct |
212 ms |
42252 KB |
Output is correct |
22 |
Correct |
206 ms |
41452 KB |
Output is correct |
23 |
Correct |
216 ms |
42096 KB |
Output is correct |
24 |
Correct |
214 ms |
41920 KB |
Output is correct |
25 |
Correct |
200 ms |
40656 KB |
Output is correct |
26 |
Correct |
204 ms |
41844 KB |
Output is correct |
27 |
Correct |
211 ms |
40428 KB |
Output is correct |
28 |
Correct |
8 ms |
10004 KB |
Output is correct |
29 |
Correct |
6 ms |
10068 KB |
Output is correct |
30 |
Correct |
6 ms |
10000 KB |
Output is correct |
31 |
Correct |
6 ms |
9940 KB |
Output is correct |
32 |
Correct |
6 ms |
9940 KB |
Output is correct |
33 |
Correct |
6 ms |
9980 KB |
Output is correct |
34 |
Correct |
6 ms |
10068 KB |
Output is correct |
35 |
Correct |
6 ms |
10068 KB |
Output is correct |
36 |
Correct |
6 ms |
10024 KB |
Output is correct |
37 |
Correct |
18 ms |
13704 KB |
Output is correct |
38 |
Correct |
189 ms |
45692 KB |
Output is correct |
39 |
Correct |
176 ms |
43116 KB |
Output is correct |
40 |
Correct |
161 ms |
40764 KB |
Output is correct |
41 |
Correct |
152 ms |
39456 KB |
Output is correct |
42 |
Correct |
144 ms |
38544 KB |
Output is correct |
43 |
Correct |
141 ms |
36160 KB |
Output is correct |
44 |
Correct |
191 ms |
44672 KB |
Output is correct |
45 |
Correct |
183 ms |
45760 KB |
Output is correct |
46 |
Correct |
147 ms |
43492 KB |
Output is correct |
47 |
Correct |
139 ms |
39288 KB |
Output is correct |
48 |
Correct |
26 ms |
14112 KB |
Output is correct |
49 |
Correct |
442 ms |
51080 KB |
Output is correct |
50 |
Correct |
413 ms |
48776 KB |
Output is correct |
51 |
Correct |
376 ms |
47512 KB |
Output is correct |
52 |
Correct |
365 ms |
46512 KB |
Output is correct |
53 |
Correct |
319 ms |
43892 KB |
Output is correct |
54 |
Correct |
213 ms |
36460 KB |
Output is correct |
55 |
Correct |
435 ms |
51676 KB |
Output is correct |
56 |
Correct |
431 ms |
52136 KB |
Output is correct |
57 |
Correct |
376 ms |
50656 KB |
Output is correct |
58 |
Correct |
300 ms |
46848 KB |
Output is correct |
59 |
Correct |
101 ms |
19104 KB |
Output is correct |
60 |
Correct |
401 ms |
48280 KB |
Output is correct |
61 |
Correct |
414 ms |
46528 KB |
Output is correct |
62 |
Correct |
443 ms |
49880 KB |
Output is correct |
63 |
Correct |
377 ms |
47396 KB |
Output is correct |
64 |
Correct |
6 ms |
9940 KB |
Output is correct |
65 |
Correct |
6 ms |
10048 KB |
Output is correct |
66 |
Correct |
6 ms |
9940 KB |
Output is correct |
67 |
Correct |
6 ms |
9812 KB |
Output is correct |
68 |
Correct |
6 ms |
9892 KB |
Output is correct |
69 |
Correct |
7 ms |
10068 KB |
Output is correct |
70 |
Correct |
6 ms |
10068 KB |
Output is correct |
71 |
Correct |
7 ms |
10068 KB |
Output is correct |
72 |
Correct |
6 ms |
10028 KB |
Output is correct |
73 |
Correct |
6 ms |
9956 KB |
Output is correct |
74 |
Correct |
131 ms |
35276 KB |
Output is correct |
75 |
Correct |
172 ms |
42332 KB |
Output is correct |
76 |
Correct |
148 ms |
39388 KB |
Output is correct |
77 |
Correct |
141 ms |
38652 KB |
Output is correct |
78 |
Correct |
62 ms |
16560 KB |
Output is correct |
79 |
Correct |
52 ms |
15860 KB |
Output is correct |
80 |
Correct |
119 ms |
30832 KB |
Output is correct |
81 |
Correct |
209 ms |
44628 KB |
Output is correct |
82 |
Correct |
187 ms |
42512 KB |
Output is correct |
83 |
Correct |
221 ms |
48140 KB |
Output is correct |
84 |
Correct |
159 ms |
44648 KB |
Output is correct |
85 |
Correct |
164 ms |
41676 KB |
Output is correct |
86 |
Correct |
74 ms |
21596 KB |
Output is correct |
87 |
Correct |
384 ms |
48376 KB |
Output is correct |
88 |
Correct |
393 ms |
48468 KB |
Output is correct |
89 |
Correct |
276 ms |
43604 KB |
Output is correct |
90 |
Correct |
146 ms |
23064 KB |
Output is correct |
91 |
Correct |
161 ms |
25204 KB |
Output is correct |
92 |
Correct |
244 ms |
38460 KB |
Output is correct |
93 |
Correct |
415 ms |
52644 KB |
Output is correct |
94 |
Correct |
316 ms |
50796 KB |
Output is correct |
95 |
Correct |
470 ms |
55904 KB |
Output is correct |
96 |
Correct |
382 ms |
49108 KB |
Output is correct |
97 |
Correct |
295 ms |
48380 KB |
Output is correct |