#include "swap.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;
const int nmax = 300005;
int pardsu[nmax], last, lca[nmax][19], marked[nmax], grad[nmax], val[nmax], timp, in[nmax], out[nmax], apropiat[nmax];
vector<pair<int, pair<int,int>>>edges;
vector<int>nod[nmax];
int findpar(int x){
if(x != pardsu[x]){
pardsu[x] = findpar(pardsu[x]);
}
return pardsu[x];
}
void dfs(int s, int apr = 0, int par = 0){
in[s] = ++timp;
if(marked[s]) apr = s;
apropiat[s] = apr;
for(auto it : nod[s]){
if(it != par){
dfs(it, apr, s);
}
}
out[s] = ++timp;
}
bool is_lca(int x, int y){
if(in[x] <= in[y] && out[x] >= out[y]) return true;
else return false;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
last = N;
for(int i=1;i<=N;i++) pardsu[i] = i;
for(int i=0;i<M;i++){
U[i]++; V[i]++;
edges.push_back({W[i], {U[i], V[i]}});
}
sort(all(edges));
for(auto it : edges){
int x = findpar(it.sc.fr);
int y = findpar(it.sc.sc);
++last;
pardsu[y] = last;
pardsu[x] = last;
pardsu[last] = last;
val[last] = it.fr;
grad[it.sc.sc]++;
grad[it.sc.fr]++;
lca[x][0] = last;
lca[y][0] = last;
nod[last].push_back(x);
if(x != y) nod[last].push_back(y);
if(x == y){
marked[last] = 1;
}
else{
if(grad[it.sc.sc] >= 3 || grad[it.sc.fr] >= 3){
marked[last] = 1;
}
}
}
for(int i=1;i<=18;i++){
for(int j=1;j<=last;j++){
lca[j][i] = lca[lca[j][i-1]][i-1];
}
}
dfs(last);
}
int getMinimumFuelCapacity(int X, int Y) {
X++;
Y++;
int curr = X;
if(!is_lca(curr, Y)){
for(int i=18;i>=0;i--){
if(lca[curr][i] != 0 && !is_lca(lca[curr][i], Y)) curr = lca[curr][i];
}
curr = lca[curr][0];
}
if(!apropiat[curr]) return -1;
else{
return val[apropiat[curr]];
}
}
Compilation message
paint.cpp:1:10: fatal error: swap.h: No such file or directory
1 | #include "swap.h"
| ^~~~~~~~
compilation terminated.
