#include <bits/stdc++.h>
using namespace std;
const int oo = INT_MAX;
vector<pair<int,int>> G[100005];
vector<pair<int,pair<int,int>>> e;
vector<int> l[100005];
vector<pair<int,int>> c[100005];
int t[100005];
int Max[100005];
multiset<int> s[100005];
int reprezentant(int nod)
{
if(t[nod]==nod)
{
return nod;
}
return reprezentant(t[nod]);
}
void uneste(int x, int y, int cost)
{
x = reprezentant(x);
y = reprezentant(y);
if(x==y)
{
return;
}
auto itx = s[x].lower_bound(cost);
s[x].erase(itx);
auto ity = s[y].lower_bound(cost);
s[y].erase(ity);
if(l[x].size() > l[y].size())
{
t[y] = x;
for(auto it=s[y].begin();it!=s[y].end();it++)
{
s[x].insert(*it);
}
Max[x] = max(Max[x],cost);
Max[x] = max(Max[x],Max[y]);
auto it = s[x].begin();
int val = 0;
if(it==s[x].end())
{
val = oo;
}
else
{
val = *it;
}
val = max(val,Max[x]);
for(auto it : l[y])
{
l[x].push_back(it);
c[it].push_back({x,val});
}
}
else
{
t[x] = y;
for(auto it=s[x].begin();it!=s[x].end();it++)
{
s[y].insert(*it);
}
Max[y] = max(Max[y],cost);
Max[y] = max(Max[y],Max[x]);
auto it =s[y].begin();
int val = 0;
if(it==s[y].end())
{
val = oo;
}
else
{
val = *it;
}
val = max(val,Max[y]);
for(auto it : l[x])
{
l[y].push_back(it);
c[it].push_back({y,val});
}
}
}
init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
for(int i=0;i<m;i++)
{
int x = u[i];
int y = v[i];
int c = w[i];
e.push_back({c,{x,y}});
G[x].push_back({y,c});
G[y].push_back({x,c});
}
sort(e.begin(),e.end());
for(int i=0;i<n;i++)
{
t[i] = i;
Max[i] = 0;
for(auto it : G[i])
{
int c = it.second;
s[i].insert(c);
}
auto it = s[i].begin();
l[i].push_back(i);
c[i].push_back({i,*it});
}
for(auto it : e)
{
int x = it.second.first;
int y = it.second.second;
int c = it.first;
uneste(x,y,c);
}
for(int i=0;i<n;i++)
{
reverse(c[i].begin(),c[i].end());
}
}
int getMinimumFuelCapacity(int x, int y)
{
int st = 0;
int dr = min(c[x].size(),c[y].size()) - 1;
int poz = 0;
while(st<=dr)
{
int mij = (st + dr) >> 1;
if(c[x][mij].first==c[y][mij].first)
{
poz = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
if(c[x][poz].second==oo || c[y][poz].second==oo)
{
return -1;
}
return max(c[x][poz].second,c[y][poz].second);
}
Compilation message
swap.cpp:93:1: error: ISO C++ forbids declaration of 'init' with no type [-fpermissive]
93 | init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
| ^~~~
swap.cpp: In function 'int init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:129:1: warning: no return statement in function returning non-void [-Wreturn-type]
129 | }
| ^
