#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
template<typename T>
ostream& operator+(ostream& out, const vector<T> &vec){
for(const auto &x : vec){
out<<x<<" ";
}
out<<"\n";
return out;
}
template<typename T>
ostream& operator*(ostream& out, const vector<T> &vec){
for(const auto &x : vec){
out+x;
}
return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
for(auto &x : vec){
in>>x;
}
return in;
}
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(0);
vector<Edge> edges;
void init(int n,int m, int u[], int v[], int w[]){
edges.resize(m);
dsu = Persistent_DSU(n);
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;
return edges[mn-1].w;
}
Compilation message
swap.cpp: In function 'int getminimumFuelCapacity(int, int)':
swap.cpp:126:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | if(mn == edges.size() + 1) return -1;
| ~~~^~~~~~~~~~~~~~~~~~~
/tmp/cc3eF3dU.o: In function `main':
grader.cpp:(.text.startup+0x1a8): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
grader.cpp:(.text.startup+0x214): undefined reference to `getMinimumFuelCapacity(int, int)'
collect2: error: ld returned 1 exit status
