#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
struct Persistent_DSU{
int n;
vector<int> par;
vector<int> partime;
struct state{
int edges, size, time;
state(int edges, int size,int time) : edges(edges), size(size), time(time) {}
state() {}
bool operator<(const state &o){
return time<o.time;
}
bool operator<(int t){
return time < t;
}
};
vector<vector<state>> sz;
int currtime = 0;
Persistent_DSU(int n) : n(n){
par.resize(n);
iota(par.begin(), par.end(), 0);
partime.assign(n, -1);
sz.assign(n, {state(0,1,0)});
}
int find_set(int u,int t){
while(par[u] != u && partime[u] < t){
u = par[u];
}
return u;
}
void join_sets(int u,int v){
int r1 = find_set(u, currtime);
int r2 = find_set(v, currtime);
if(r1 == r2){
auto s = sz[r1].back();
s.edges++;
s.time = currtime;
sz[r1].push_back(s);
++currtime;
return;
}
auto [e1,s1,t1] = sz[r1].back();
auto [e2,s2,t2] = sz[r2].back();
if(s1 > s2){
swap(r1,r2);
}
par[r1] = r2;
partime[r1] = currtime;
sz[r2].push_back(state(e1+e2+1,s1+s2,currtime));
++currtime;
}
state findstate(int u,int t){
auto it = lower_bound(sz[u].begin(), sz[u].end(), t);
--it;
return (*it);
}
};
const int INF = 1e9;
struct Edge{
int u,v,w;
Edge(int u,int v,int w) : u(u), v(v), w(w) {}
Edge() {}
bool operator<(const Edge &o){
return w < o.w;
}
};
Persistent_DSU dsu;
vector<Edge> edges;
int init(int n,int m, int u[], int v[], int w[]){
edges.resize(m);
for(int i=0;i<m;i++){
edges[i] = Edge(u[i],v[i],w[i]);
}
Persistent_DSU dsu(n);
sort(edges.begin(), edges.end());
for(const auto &[u,v,w] : edges){
dsu.join_sets(u,v);
}
}
int getminimumFuelCapacity(int x,int y){
int mn = 1, mx = edges.size() + 1;
while(mn < mx){
int mid = mn + mx;
mid>>=1;
int r1 = dsu.find_set(x, mid);
int r2 = dsu.find_set(y, mid);
if(r1 != r2){
mn = mid + 1;
continue;
}
auto s = dsu.findstate(r1, mid);
if(s.edges < s.size){
mn = mid + 1;
}
else{
mx = mid;
}
}
if(mn == edges.size() + 1) return -1;
else return edges[mn-1].w;
}
Compilation message
swap.cpp:71:16: error: no matching function for call to 'Persistent_DSU::Persistent_DSU()'
71 | Persistent_DSU dsu;
| ^~~
swap.cpp:23:5: note: candidate: 'Persistent_DSU::Persistent_DSU(int)'
23 | Persistent_DSU(int n) : n(n){
| ^~~~~~~~~~~~~~
swap.cpp:23:5: note: candidate expects 1 argument, 0 provided
swap.cpp:6:8: note: candidate: 'Persistent_DSU::Persistent_DSU(const Persistent_DSU&)'
6 | struct Persistent_DSU{
| ^~~~~~~~~~~~~~
swap.cpp:6:8: note: candidate expects 1 argument, 0 provided
swap.cpp:6:8: note: candidate: 'Persistent_DSU::Persistent_DSU(Persistent_DSU&&)'
swap.cpp:6:8: note: candidate expects 1 argument, 0 provided
swap.cpp: In function 'int init(int, int, int*, int*, int*)':
swap.cpp:83:1: warning: no return statement in function returning non-void [-Wreturn-type]
83 | }
| ^
swap.cpp: In function 'int getminimumFuelCapacity(int, int)':
swap.cpp:103:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | if(mn == edges.size() + 1) return -1;
| ~~~^~~~~~~~~~~~~~~~~~~
