#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e9 + 37;
vector<vector<int> > g; // {to, c}
struct Edge
{
int from, to, c;
Edge() { }
Edge(int u, int v, int w) : from(u), to(v), c(w) {
}
const bool operator<(const Edge& other) const {
return c < other.c;
}
};
struct Node
{
bool is_line = true;
array<int, 2> endpoints;
int par, size, w;
Node(int u) : endpoints({u, u}), par(u), size(1), w(inf) {
}
};
vector<Node> dsu;
vector<Edge> edges;
int idx = -1;
int get_root(int v) { // currently slow
return (dsu[v].par == v ? v : dsu[v].par = get_root(dsu[v].par));
}
void merge(int u, int v, int c) {
int paru = get_root(u), parv = get_root(v);
if(paru == parv) {
dsu[paru].is_line = false;
dsu[paru].w = min(dsu[paru].w, c);
return;
}
if(dsu[paru].size > dsu[parv].size) {
swap(u, v);
swap(paru, parv);
}
int cur_node = dsu.size();
dsu.emplace_back(Node(cur_node));
if(find(dsu[paru].endpoints.begin(), dsu[paru].endpoints.end(), u) != dsu[paru].endpoints.end() and
find(dsu[parv].endpoints.begin(), dsu[parv].endpoints.end(), v) != dsu[parv].endpoints.end()) {
dsu[cur_node].endpoints = {dsu[paru].endpoints[dsu[paru].endpoints[0] == u], dsu[parv].endpoints[dsu[parv].endpoints[0] == v]};
}
else {
dsu[cur_node].endpoints = {-1, -1};
dsu[cur_node].is_line = false;
dsu[cur_node].w = min(dsu[cur_node].w, c);
}
dsu[paru].par = dsu[parv].par = cur_node;
dsu[cur_node].size = dsu[paru].size + dsu[parv].size;
}
vector<vector<int> > fa;
vector<int> dep;
const int LOG = 20;
void init_lca() {
int n = dsu.size();
fa.assign(n, vector<int>(LOG, -1));
dep.assign(n, -1);
g.assign(n, vector<int>());
for(int i = 0; i < n; ++i) {
if(dsu[i].par == i)
continue;
fa[i][0] = (dsu[i].par == i ? -1 : dsu[i].par);
}
for(int j = 1; j < LOG; ++j) {
for(int i = 0; i < n; ++i) {
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
// cout << "wtf1\n";
edges.assign(M, Edge());
for(int i = 0; i < M; ++i) {
edges[i] = {U[i], V[i], W[i]};
}
// cout << "wtf2\n";
sort(edges.begin(), edges.end());
for(int i = 0; i < N; ++i) {
dsu.emplace_back(Node(i));
}
// cout << "wtf3\n";
for(const Edge& e : edges) {
merge(e.from, e.to, e.c);
}
// cout << "wtf4\n";
// int len = dsu.size();
// for(int i = 0; i < len; ++i) {
// cout << i << " : " << dsu[i].par << ' ' << dsu[i].w << endl;
// }
}
int getMinimumFuelCapacity(int X, int Y) {
if(get_root(X) != get_root(Y)) {
return -1;
}
return 37;
}
| # |
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 |
- |
