#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int tsz;
struct DSU {
int n;
vector<int> parent, sz;
vector<bool> chain;
vector<vector<int>> comp;
vector<int> id;
DSU(int _n) {
n = _n;
parent.resize(n);
sz.resize(n);
comp.resize(n);
chain.resize(n);
id.resize(n);
for(int i = 0; i < n; i++) {
parent[i] = i;
sz[i] = 1;
chain[i] = true;
comp[i].push_back(i);
id[i] = i;
}
}
int find_parent(int u) {
if(parent[u] == u) return u;
return parent[u] = find_parent(parent[u]);
}
bool check(int u, int v) {
u = find_parent(u);
v = find_parent(v);
return u == v;
}
void join(int u, int v) {
u = find_parent(u);
v = find_parent(v);
if(sz[u] > sz[v]) swap(u, v);
for(int i : comp[u]) comp[v].push_back(i);
comp[u].clear();
parent[u] = v;
sz[v] += sz[u];
id[v] = tsz;
}
void update_chain_state(int u) {
u = find_parent(u);
chain[u] = false;
}
int get_size(int u) {
u = find_parent(u);
return sz[u];
}
};
const int N = 2e6 + 10, LOG = 20;
bool leaf[N];
DSU dsu(N), tree(2 * N);
int order[2 * N];
vector<int> g[2 * N];
int up[2 * N][LOG + 1];
int root;
int timer;
int tin[2 * N], tout[2 * N];
int ans[2 * N];
bool mark[2 * N];
void dfs(int u) {
mark[u] = true;
tin[u] = ++timer;
for(int v : g[u]) {
dfs(v);
up[v][0] = u;
}
tout[u] = ++timer;
}
bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int LCA(int u, int v) {
if(is_ancestor(u, v)) return u;
if(is_ancestor(v, u)) return v;
for(int j = LOG; j >= 0; j--) {
// cout << up[u][j] << "\n";
if(up[u][j] == -1) continue;
if(is_ancestor(up[u][j], v)) continue;
u = up[u][j];
// cout << u << " " << j << "\n";
}
return up[u][0];
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
for(int i = 0; i < N; i++) {
leaf[i] = true;
for(int j = 0; j <= LOG; j++) up[i][j] = -1;
}
tsz = n;
for(int i = 0; i < m; i++) order[i] = i;
sort(order, order + m, [&](int i, int j) { return W[i] < W[j]; });
for(int i = 0; i < m; i++) {
int u = U[order[i]], v = V[order[i]];
if(dsu.check(u, v)) {
int par = dsu.find_parent(u);
if(dsu.chain[par]) {
for(int j : dsu.comp[par]) {
g[tsz].push_back(j);
tree.join(tsz, j);
}
ans[tsz] = W[order[i]];
dsu.id[par] = tsz;
tsz++;
dsu.update_chain_state(par);
}
} else {
if(!dsu.chain[dsu.find_parent(u)] || !dsu.chain[dsu.find_parent(v)]) {
if(dsu.chain[dsu.find_parent(u)]) {
for(int j : dsu.comp[dsu.find_parent(u)]) {
g[tsz].push_back(j);
tree.join(tsz, j);
}
} else {
g[tsz].push_back(dsu.id[dsu.find_parent(u)]);
tree.join(tsz, dsu.id[dsu.find_parent(u)]);
}
if(dsu.chain[dsu.find_parent(v)]) {
for(int j : dsu.comp[dsu.find_parent(v)]) {
g[tsz].push_back(j);
tree.join(tsz, j);
}
} else {
g[tsz].push_back(dsu.id[dsu.find_parent(v)]);
tree.join(tsz, dsu.id[dsu.find_parent(v)]);
}
dsu.join(u, v);
ans[tsz] = W[order[i]];
tsz++;
} else {
if(leaf[u] && leaf[v]) {
if(dsu.get_size(u) > 1) leaf[u] = false;
if(dsu.get_size(v) > 1) leaf[v] = false;
dsu.join(u, v);
} else {
for(int j : dsu.comp[dsu.find_parent(u)]) {
g[tsz].push_back(j);
tree.join(tsz, j);
}
for(int j : dsu.comp[dsu.find_parent(v)]) {
g[tsz].push_back(j);
tree.join(tsz, j);
}
dsu.join(u, v);
ans[tsz] = W[order[i]];
tsz++;
dsu.update_chain_state(u);
}
}
}
}
// for(int i = 0; i < tsz; i++) {
// cout << i << ": ";
// for(int j : g[i]) cout << j << " ";
// cout << "\n";
// }
root = tsz - 1;
for(int i = root; i >= 0; i--) if(!mark[i]) dfs(i);
// for(int i = 0; i <= root; i++) {
// for(int j = 0; j <= 5; j++) cout << up[i][j] << " ";
// cout << "\n";
// }
for(int j = 1; j <= LOG; j++) {
for(int i = 0; i <= root; i++) {
if(up[i][j - 1] == -1) up[i][j] = -1;
else up[i][j] = up[up[i][j - 1]][j - 1];
}
}
// cout << "TU: " << LCA(4, 5) << "\n";
}
int getMinimumFuelCapacity(int X, int Y) {
// return -1;
if(!tree.check(X, Y)) return -1;
return ans[LCA(X, Y)];
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
3 2
0 1 5
0 2 5
1
1 2
6 7
0 1 1
1 2 2
0 2 3
3 4 4
4 5 5
3 5 6
2 3 7
15
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
