#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;
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 = 1e5 + 10, LOG = 17;
bool leaf[N];
DSU dsu(N);
int order[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];
void dfs(int u, int par) {
tin[u] = ++timer;
for(int v : g[u]) {
dfs(v, u);
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 - 1; j >= 0; j--) {
if(up[u][j] == 0) continue;
if(is_ancestor(up[u][j], v)) continue;
u = up[u][j];
}
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;
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);
}
ans[tsz] = W[order[i]];
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);
} else g[tsz].push_back(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);
} else g[tsz].push_back(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);
for(int j : dsu.comp[dsu.find_parent(v)]) g[tsz].push_back(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;
dfs(root, -1);
for(int j = 1; j < LOG; j++) for(int i = 0; i <= root; i++) up[i][j] = up[up[i][j - 1]][j - 1];
}
int getMinimumFuelCapacity(int X, int Y) {
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
17836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
17836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
17836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
17836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
17836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
17836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
