#pragma GCC optimize("Ofast,O3,unroll-loops")
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MaxN = 100002;
const int MaxM = 200002;
int N, M;
const int blockLength = 700;
struct Set{
int parent;
bool line;
pair<int, int> tail;
Set(){};
Set(int i){
parent = i;
line = true;
tail = make_pair(i, i);
}
};
Set t[MaxN];
int MAGIC;
bool flag[MaxN];
Set mem[MaxN][MaxM / blockLength + 3];
int re[MaxN];
int _nxt;
int leader(int x){
if (MAGIC != -1 && !flag[x]){
t[x] = (MAGIC == 0 ? Set(x) : mem[x][MAGIC - 1]);
flag[x] = true;
re[_nxt++] = x;
}
return t[x].parent == x ? x : t[x].parent = leader(t[x].parent);
}
void unite(int x, int y){
int X = x, Y = y;
x = leader(x);
y = leader(y);
if (rng() & 1){
swap(x, y);
swap(X, Y);
}
if (x == y){
t[y].line = false;
return;
}
t[x].parent = y;
if (!t[x].line){
t[y].line = false;
return;
}
if (!t[y].line) return;
if (t[x].tail.first != X && t[x].tail.second != X){
t[y].line = false;
return;
}
if (t[y].tail.first != Y && t[y].tail.second != Y){
t[y].line = false;
return;
}
pair<int, int> new_tail;
new_tail.first = t[x].tail.first ^ t[x].tail.second ^ X;
new_tail.second = t[y].tail.first ^ t[y].tail.second ^ Y;
t[y].tail = new_tail;
}
int el[MaxM], er[MaxM];
int blockCount;
tuple<int, int, int> edges[MaxM];
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
N = _N, M = _M;
for (int i = 0; i < M; i++){
edges[i] = make_tuple(W[i], U[i], V[i]);
}
sort(edges, edges + M);
for (int i = 0; i < N; i++) t[i] = Set(i);
MAGIC = -1;
blockCount = 0;
for (int i = 0; i < M; i++){
int u = get<1>(edges[i]), v = get<2>(edges[i]);
unite(u, v);
if ((i + 1) % blockLength == 0 || i == M - 1){
int id = blockCount++;
el[id] = 0, er[id] = i;
if (id > 0) el[id] = er[id - 1] + 1;
for (int j = 0; j < N; j++) mem[j][id] = t[leader(j)];
}
}
for (int i = 0; i < N; i++) flag[i] = false;
}
bool can(int x, int y){
x = leader(x);
y = leader(y);
return x == y && !t[x].line;
}
int getMinimumFuelCapacity(int X, int Y) {
int id = 0;
while (id < blockCount){
int xx = mem[X][id].parent, yy = mem[Y][id].parent;
if (xx == yy && !mem[xx][id].line){
break;
} else {
id++;
}
}
if (id == blockCount) return -1;
MAGIC = id;
int ans = -1;
_nxt = 0;
for (int i = el[id]; i <= er[id]; i++){
auto [w, u, v] = edges[i];
unite(u, v);
if (can(X, Y)){
ans = w;
break;
}
}
for (int i = 0; i < _nxt; i++) flag[re[i]] = false;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
452764 KB |
Output is correct |
2 |
Correct |
209 ms |
452744 KB |
Output is correct |
3 |
Correct |
200 ms |
452684 KB |
Output is correct |
4 |
Correct |
204 ms |
452824 KB |
Output is correct |
5 |
Correct |
208 ms |
452724 KB |
Output is correct |
6 |
Correct |
207 ms |
452816 KB |
Output is correct |
7 |
Correct |
211 ms |
452812 KB |
Output is correct |
8 |
Correct |
218 ms |
452812 KB |
Output is correct |
9 |
Correct |
396 ms |
456208 KB |
Output is correct |
10 |
Correct |
570 ms |
456820 KB |
Output is correct |
11 |
Correct |
517 ms |
456792 KB |
Output is correct |
12 |
Correct |
598 ms |
456964 KB |
Output is correct |
13 |
Correct |
571 ms |
456964 KB |
Output is correct |
14 |
Correct |
449 ms |
456416 KB |
Output is correct |
15 |
Correct |
730 ms |
458552 KB |
Output is correct |
16 |
Correct |
676 ms |
458500 KB |
Output is correct |
17 |
Correct |
787 ms |
458592 KB |
Output is correct |
18 |
Correct |
718 ms |
458576 KB |
Output is correct |
19 |
Execution timed out |
2080 ms |
455664 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
452764 KB |
Output is correct |
2 |
Correct |
209 ms |
452744 KB |
Output is correct |
3 |
Execution timed out |
2070 ms |
458196 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
452764 KB |
Output is correct |
2 |
Correct |
209 ms |
452744 KB |
Output is correct |
3 |
Correct |
200 ms |
452684 KB |
Output is correct |
4 |
Correct |
204 ms |
452824 KB |
Output is correct |
5 |
Correct |
208 ms |
452724 KB |
Output is correct |
6 |
Correct |
207 ms |
452816 KB |
Output is correct |
7 |
Correct |
211 ms |
452812 KB |
Output is correct |
8 |
Correct |
218 ms |
452812 KB |
Output is correct |
9 |
Correct |
207 ms |
452664 KB |
Output is correct |
10 |
Correct |
205 ms |
452788 KB |
Output is correct |
11 |
Correct |
220 ms |
452744 KB |
Output is correct |
12 |
Correct |
205 ms |
452820 KB |
Output is correct |
13 |
Correct |
214 ms |
452756 KB |
Output is correct |
14 |
Correct |
204 ms |
452700 KB |
Output is correct |
15 |
Correct |
204 ms |
452732 KB |
Output is correct |
16 |
Correct |
202 ms |
452816 KB |
Output is correct |
17 |
Correct |
216 ms |
452748 KB |
Output is correct |
18 |
Correct |
204 ms |
452880 KB |
Output is correct |
19 |
Correct |
204 ms |
452788 KB |
Output is correct |
20 |
Correct |
197 ms |
452812 KB |
Output is correct |
21 |
Correct |
203 ms |
452784 KB |
Output is correct |
22 |
Correct |
201 ms |
452804 KB |
Output is correct |
23 |
Correct |
205 ms |
452812 KB |
Output is correct |
24 |
Correct |
205 ms |
452844 KB |
Output is correct |
25 |
Correct |
212 ms |
452876 KB |
Output is correct |
26 |
Correct |
216 ms |
452808 KB |
Output is correct |
27 |
Correct |
205 ms |
452776 KB |
Output is correct |
28 |
Correct |
202 ms |
452808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
207 ms |
452664 KB |
Output is correct |
2 |
Correct |
205 ms |
452764 KB |
Output is correct |
3 |
Correct |
209 ms |
452744 KB |
Output is correct |
4 |
Correct |
200 ms |
452684 KB |
Output is correct |
5 |
Correct |
204 ms |
452824 KB |
Output is correct |
6 |
Correct |
208 ms |
452724 KB |
Output is correct |
7 |
Correct |
207 ms |
452816 KB |
Output is correct |
8 |
Correct |
211 ms |
452812 KB |
Output is correct |
9 |
Correct |
218 ms |
452812 KB |
Output is correct |
10 |
Correct |
396 ms |
456208 KB |
Output is correct |
11 |
Correct |
570 ms |
456820 KB |
Output is correct |
12 |
Correct |
517 ms |
456792 KB |
Output is correct |
13 |
Correct |
598 ms |
456964 KB |
Output is correct |
14 |
Correct |
571 ms |
456964 KB |
Output is correct |
15 |
Correct |
205 ms |
452788 KB |
Output is correct |
16 |
Correct |
220 ms |
452744 KB |
Output is correct |
17 |
Correct |
205 ms |
452820 KB |
Output is correct |
18 |
Correct |
214 ms |
452756 KB |
Output is correct |
19 |
Correct |
204 ms |
452700 KB |
Output is correct |
20 |
Correct |
204 ms |
452732 KB |
Output is correct |
21 |
Correct |
202 ms |
452816 KB |
Output is correct |
22 |
Correct |
216 ms |
452748 KB |
Output is correct |
23 |
Correct |
204 ms |
452880 KB |
Output is correct |
24 |
Correct |
204 ms |
452788 KB |
Output is correct |
25 |
Correct |
197 ms |
452812 KB |
Output is correct |
26 |
Correct |
203 ms |
452784 KB |
Output is correct |
27 |
Correct |
201 ms |
452804 KB |
Output is correct |
28 |
Correct |
205 ms |
452812 KB |
Output is correct |
29 |
Correct |
205 ms |
452844 KB |
Output is correct |
30 |
Correct |
212 ms |
452876 KB |
Output is correct |
31 |
Correct |
216 ms |
452808 KB |
Output is correct |
32 |
Correct |
205 ms |
452776 KB |
Output is correct |
33 |
Correct |
202 ms |
452808 KB |
Output is correct |
34 |
Correct |
215 ms |
453252 KB |
Output is correct |
35 |
Correct |
509 ms |
456548 KB |
Output is correct |
36 |
Correct |
512 ms |
456524 KB |
Output is correct |
37 |
Correct |
508 ms |
456564 KB |
Output is correct |
38 |
Correct |
619 ms |
456400 KB |
Output is correct |
39 |
Correct |
603 ms |
456464 KB |
Output is correct |
40 |
Correct |
540 ms |
456084 KB |
Output is correct |
41 |
Correct |
549 ms |
456440 KB |
Output is correct |
42 |
Correct |
508 ms |
456440 KB |
Output is correct |
43 |
Correct |
513 ms |
456444 KB |
Output is correct |
44 |
Correct |
527 ms |
456440 KB |
Output is correct |
45 |
Correct |
626 ms |
458216 KB |
Output is correct |
46 |
Correct |
526 ms |
456508 KB |
Output is correct |
47 |
Correct |
524 ms |
456448 KB |
Output is correct |
48 |
Correct |
581 ms |
456848 KB |
Output is correct |
49 |
Correct |
271 ms |
458444 KB |
Output is correct |
50 |
Correct |
261 ms |
457136 KB |
Output is correct |
51 |
Correct |
515 ms |
457456 KB |
Output is correct |
52 |
Correct |
773 ms |
458604 KB |
Output is correct |
53 |
Correct |
841 ms |
459216 KB |
Output is correct |
54 |
Correct |
864 ms |
459972 KB |
Output is correct |
55 |
Correct |
521 ms |
456440 KB |
Output is correct |
56 |
Correct |
792 ms |
458964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
452764 KB |
Output is correct |
2 |
Correct |
209 ms |
452744 KB |
Output is correct |
3 |
Correct |
200 ms |
452684 KB |
Output is correct |
4 |
Correct |
204 ms |
452824 KB |
Output is correct |
5 |
Correct |
208 ms |
452724 KB |
Output is correct |
6 |
Correct |
207 ms |
452816 KB |
Output is correct |
7 |
Correct |
211 ms |
452812 KB |
Output is correct |
8 |
Correct |
218 ms |
452812 KB |
Output is correct |
9 |
Correct |
396 ms |
456208 KB |
Output is correct |
10 |
Correct |
570 ms |
456820 KB |
Output is correct |
11 |
Correct |
517 ms |
456792 KB |
Output is correct |
12 |
Correct |
598 ms |
456964 KB |
Output is correct |
13 |
Correct |
571 ms |
456964 KB |
Output is correct |
14 |
Correct |
449 ms |
456416 KB |
Output is correct |
15 |
Correct |
730 ms |
458552 KB |
Output is correct |
16 |
Correct |
676 ms |
458500 KB |
Output is correct |
17 |
Correct |
787 ms |
458592 KB |
Output is correct |
18 |
Correct |
718 ms |
458576 KB |
Output is correct |
19 |
Execution timed out |
2070 ms |
458196 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
207 ms |
452664 KB |
Output is correct |
2 |
Correct |
205 ms |
452764 KB |
Output is correct |
3 |
Correct |
209 ms |
452744 KB |
Output is correct |
4 |
Correct |
200 ms |
452684 KB |
Output is correct |
5 |
Correct |
204 ms |
452824 KB |
Output is correct |
6 |
Correct |
208 ms |
452724 KB |
Output is correct |
7 |
Correct |
207 ms |
452816 KB |
Output is correct |
8 |
Correct |
211 ms |
452812 KB |
Output is correct |
9 |
Correct |
218 ms |
452812 KB |
Output is correct |
10 |
Correct |
396 ms |
456208 KB |
Output is correct |
11 |
Correct |
570 ms |
456820 KB |
Output is correct |
12 |
Correct |
517 ms |
456792 KB |
Output is correct |
13 |
Correct |
598 ms |
456964 KB |
Output is correct |
14 |
Correct |
571 ms |
456964 KB |
Output is correct |
15 |
Correct |
449 ms |
456416 KB |
Output is correct |
16 |
Correct |
730 ms |
458552 KB |
Output is correct |
17 |
Correct |
676 ms |
458500 KB |
Output is correct |
18 |
Correct |
787 ms |
458592 KB |
Output is correct |
19 |
Correct |
718 ms |
458576 KB |
Output is correct |
20 |
Execution timed out |
2070 ms |
458196 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |