#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int)1e9 + 7;
vector<int> t;
vector<int> dim;
vector<int> is_line;
vector<int> when;
vector<int> endpoint;
vector<int> when_join;
int n, m;
void clr() {
t.resize(n);
dim.resize(n);
is_line.resize(n);
when.resize(n);
endpoint.resize(n);
when_join.resize(n);
for (int i = 0; i < n; i++) {
t[i] = i;
dim[i] = 1;
is_line[i] = 1;
when_join[i] = 1;
when[i] = -1;
}
}
int root(int a) {
if (a == t[a]) {
return a;
}
else {
return root(t[a]);
}
}
void join(int a, int b, int val) {
int x = a, y = b;
a = root(a);
b = root(b);
if (a == b) {
if (is_line[a] == 1) {
when[a] = val;
}
is_line[a] = 0;
return;
}
if (dim[a] < dim[b]) {
swap(a, b);
swap(x, y);
}
if (is_line[a] && is_line[b] && endpoint[x] && endpoint[y]) {
is_line[a] = 1;
if (dim[a] > 1) {
endpoint[x] = 0;
}
if (dim[b] > 1) {
endpoint[y] = 0;
}
}
else {
if (is_line[a] == 1) {
when[a] = val;
is_line[a] = 0;
}
}
when_join[b] = val;
dim[a] += dim[b];
t[b] = a;
}
struct Edge {
int a;
int b;
int w;
};
bool operator < (Edge a, Edge b) {
return a.w < b.w;
}
vector<Edge> edges;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
assert((int)U.size() == M);
assert((int)V.size() == M);
assert((int)W.size() == M);
n = N;
m = M;
edges.clear();
for (int i = 0; i < m; i++) {
edges.push_back({U[i], V[i], W[i]});
}
sort(edges.begin(), edges.end());
clr();
for (auto& edg : edges) {
join(edg.a, edg.b, edg.w);
}
}
int getMinimumFuelCapacity(int x, int y) {
if (x == y) {
return 0;
}
vector<int> path_x, path_y;
while (1) {
path_x.push_back(x);
if (x == t[x]) {
break;
}
x = t[x];
}
while (1) {
path_y.push_back(y);
if (y == t[y]) {
break;
}
y = t[y];
}
reverse(path_x.begin(), path_x.end());
reverse(path_y.begin(), path_y.end());
bool deja = 0;
int wjoin = 0;
for (int i = max((int) path_x.size() - 1, (int) path_y.size() -1); i >= 0; i--) {
if (i < (int) path_x.size() && i < (int) path_y.size() && path_x[i] == path_y[i]) {
if (deja) {
return wjoin;
}
if (when[path_x[i]] != -1) {
return max(wjoin, when[path_x[i]]);
}
}
if (i < (int) path_x.size()) {
if (when[path_x[i]] != -1) deja = 1;
wjoin = max(wjoin, when_join[path_x[i]]);
}
if (i < (int) path_y.size()) {
if (when[path_y[i]] != -1) deja = 1;
wjoin = max(wjoin, when_join[path_y[i]]);
}
}
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
