#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100005;
int N, M;
const int blockLength = 800;
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][MaxN / blockLength + 4];
vector<int> re; /// Todo: change to static array
int leader(int x){
if (MAGIC != -1 && !flag[x]){
t[x] = (MAGIC == 0 ? Set(x) : mem[x][MAGIC - 1]);
flag[x] = true;
re.push_back(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 (x == y){
t[y].line = false;
return;
}
if (rand() & 1){
swap(x, y);
swap(X, Y);
}
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[MaxN], er[MaxN];
int blockCount;
vector<tuple<int, int, int>> edges;
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.emplace_back(W[i], U[i], V[i]);
}
sort(edges.begin(), edges.end());
for (int i = 0; i < N; i++) t[i] = Set(i);
MAGIC = -1;
blockCount = 0;
for (int i = 0; i < M; i++){
unite(U[i], V[i]);
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;
re.clear();
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 : re) flag[i] = false;
assert(ans != -1);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
203776 KB |
Output is correct |
2 |
Correct |
79 ms |
203828 KB |
Output is correct |
3 |
Correct |
78 ms |
203784 KB |
Output is correct |
4 |
Correct |
78 ms |
203736 KB |
Output is correct |
5 |
Correct |
85 ms |
203812 KB |
Output is correct |
6 |
Correct |
87 ms |
203768 KB |
Output is correct |
7 |
Correct |
80 ms |
203968 KB |
Output is correct |
8 |
Correct |
81 ms |
203852 KB |
Output is correct |
9 |
Correct |
254 ms |
207264 KB |
Output is correct |
10 |
Correct |
351 ms |
207668 KB |
Output is correct |
11 |
Correct |
365 ms |
207632 KB |
Output is correct |
12 |
Correct |
353 ms |
207816 KB |
Output is correct |
13 |
Correct |
440 ms |
207812 KB |
Output is correct |
14 |
Correct |
253 ms |
207444 KB |
Output is correct |
15 |
Correct |
479 ms |
209312 KB |
Output is correct |
16 |
Correct |
468 ms |
209176 KB |
Output is correct |
17 |
Correct |
535 ms |
209488 KB |
Output is correct |
18 |
Correct |
551 ms |
209352 KB |
Output is correct |
19 |
Runtime error |
276 ms |
418300 KB |
Execution killed with signal 6 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
203776 KB |
Output is correct |
2 |
Correct |
79 ms |
203828 KB |
Output is correct |
3 |
Runtime error |
630 ms |
422360 KB |
Execution killed with signal 6 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
203776 KB |
Output is correct |
2 |
Correct |
79 ms |
203828 KB |
Output is correct |
3 |
Correct |
78 ms |
203784 KB |
Output is correct |
4 |
Correct |
78 ms |
203736 KB |
Output is correct |
5 |
Correct |
85 ms |
203812 KB |
Output is correct |
6 |
Correct |
87 ms |
203768 KB |
Output is correct |
7 |
Correct |
80 ms |
203968 KB |
Output is correct |
8 |
Correct |
81 ms |
203852 KB |
Output is correct |
9 |
Correct |
88 ms |
203812 KB |
Output is correct |
10 |
Runtime error |
273 ms |
413156 KB |
Execution killed with signal 6 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
203812 KB |
Output is correct |
2 |
Correct |
77 ms |
203776 KB |
Output is correct |
3 |
Correct |
79 ms |
203828 KB |
Output is correct |
4 |
Correct |
78 ms |
203784 KB |
Output is correct |
5 |
Correct |
78 ms |
203736 KB |
Output is correct |
6 |
Correct |
85 ms |
203812 KB |
Output is correct |
7 |
Correct |
87 ms |
203768 KB |
Output is correct |
8 |
Correct |
80 ms |
203968 KB |
Output is correct |
9 |
Correct |
81 ms |
203852 KB |
Output is correct |
10 |
Correct |
254 ms |
207264 KB |
Output is correct |
11 |
Correct |
351 ms |
207668 KB |
Output is correct |
12 |
Correct |
365 ms |
207632 KB |
Output is correct |
13 |
Correct |
353 ms |
207816 KB |
Output is correct |
14 |
Correct |
440 ms |
207812 KB |
Output is correct |
15 |
Runtime error |
273 ms |
413156 KB |
Execution killed with signal 6 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
203776 KB |
Output is correct |
2 |
Correct |
79 ms |
203828 KB |
Output is correct |
3 |
Correct |
78 ms |
203784 KB |
Output is correct |
4 |
Correct |
78 ms |
203736 KB |
Output is correct |
5 |
Correct |
85 ms |
203812 KB |
Output is correct |
6 |
Correct |
87 ms |
203768 KB |
Output is correct |
7 |
Correct |
80 ms |
203968 KB |
Output is correct |
8 |
Correct |
81 ms |
203852 KB |
Output is correct |
9 |
Correct |
254 ms |
207264 KB |
Output is correct |
10 |
Correct |
351 ms |
207668 KB |
Output is correct |
11 |
Correct |
365 ms |
207632 KB |
Output is correct |
12 |
Correct |
353 ms |
207816 KB |
Output is correct |
13 |
Correct |
440 ms |
207812 KB |
Output is correct |
14 |
Correct |
253 ms |
207444 KB |
Output is correct |
15 |
Correct |
479 ms |
209312 KB |
Output is correct |
16 |
Correct |
468 ms |
209176 KB |
Output is correct |
17 |
Correct |
535 ms |
209488 KB |
Output is correct |
18 |
Correct |
551 ms |
209352 KB |
Output is correct |
19 |
Runtime error |
630 ms |
422360 KB |
Execution killed with signal 6 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
203812 KB |
Output is correct |
2 |
Correct |
77 ms |
203776 KB |
Output is correct |
3 |
Correct |
79 ms |
203828 KB |
Output is correct |
4 |
Correct |
78 ms |
203784 KB |
Output is correct |
5 |
Correct |
78 ms |
203736 KB |
Output is correct |
6 |
Correct |
85 ms |
203812 KB |
Output is correct |
7 |
Correct |
87 ms |
203768 KB |
Output is correct |
8 |
Correct |
80 ms |
203968 KB |
Output is correct |
9 |
Correct |
81 ms |
203852 KB |
Output is correct |
10 |
Correct |
254 ms |
207264 KB |
Output is correct |
11 |
Correct |
351 ms |
207668 KB |
Output is correct |
12 |
Correct |
365 ms |
207632 KB |
Output is correct |
13 |
Correct |
353 ms |
207816 KB |
Output is correct |
14 |
Correct |
440 ms |
207812 KB |
Output is correct |
15 |
Correct |
253 ms |
207444 KB |
Output is correct |
16 |
Correct |
479 ms |
209312 KB |
Output is correct |
17 |
Correct |
468 ms |
209176 KB |
Output is correct |
18 |
Correct |
535 ms |
209488 KB |
Output is correct |
19 |
Correct |
551 ms |
209352 KB |
Output is correct |
20 |
Runtime error |
630 ms |
422360 KB |
Execution killed with signal 6 |
21 |
Halted |
0 ms |
0 KB |
- |