#include<bits/stdc++.h>
#include "swap.h"
#define MAXN 200007
using namespace std;
const int inf=1e9+7;
int n,m;
struct edge{
int from,to,cost;
inline friend bool operator < (edge fr,edge sc){
return fr.cost<sc.cost;
}
}e[MAXN];
int closest[MAXN],special[MAXN],parent[MAXN];
int lt[MAXN],rt[MAXN],in[MAXN],out[MAXN],num;
vector<int> query[MAXN];
vector<int> tree[MAXN],edges;
bool treeedge[MAXN];
struct union_find{
vector< pair<int,int> > dsu[MAXN];
int sz[MAXN],trip[MAXN],deg[MAXN],tim,topv[MAXN];
void reset(){
for(int i=1;i<=n;i++){
dsu[i]={{i,0}}; sz[i]=1; trip[i]=deg[i]=0;
topv[i]=i;
}
tim=0;
}
int root(int x){
if(dsu[x].back().first==x)return dsu[x].back().first;
return root(dsu[x].back().first);
}
void mergev(int x,int y){
tim++;
int rootx=root(x);
int rooty=root(y);
deg[x]++; deg[y]++;
if(deg[x]>=3)trip[rootx]=x;
if(deg[y]>=3)trip[rootx]=y;
if(rootx==rooty)return;
if(sz[rootx]<sz[rooty])swap(rootx,rooty);
dsu[rooty].push_back({rootx,tim});
sz[rootx]+=sz[rooty];
if(trip[rooty]!=0)trip[rootx]=trip[rooty];
if(in[topv[rooty]]<in[topv[rootx]])topv[rootx]=topv[rooty];
}
int comp(int x,int when){
int l=0,r=dsu[x].size(),tt;
while(l+1<r){
tt=(l+r)/2;
if(dsu[x][tt].second<=when){
l=tt;
}else{
r=tt;
}
}
return dsu[x][l].first;
}
int pastroot(int x,int when){
int curr=comp(x,when);
if(curr==x)return x;
return pastroot(curr,when);
}
}graph,bcc;
void build_mst(){
graph.reset();
for(int i=1;i<=m;i++){
graph.mergev(e[i].from,e[i].to);
for(int f:query[i]){
closest[f]=graph.trip[graph.root(f)];
}
}
}
void dfs(int x,int p){
parent[x]=p;
num++; in[x]=num;
for(int i:tree[x]){
if(i==p)continue;
dfs(i,x);
}
out[x]=num;
}
bool subtree(int x,int y){
return in[y]>=in[x] and out[y]<=out[x];
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
n=N; m=M;
for(int i=1;i<=m;i++){
e[i]={U[i-1]+1,V[i-1]+1,W[i-1]};
}
sort(e+1,e+m+1);
for(int i=1;i<=n;i++){
lt[i]=0; rt[i]=m+1;
}
for(int i=1;i<=18;i++){
for(int f=1;f<=m;f++)query[f].clear();
for(int f=1;f<=n;f++){
query[(lt[f]+rt[f])/2].push_back(f);
}
build_mst();
for(int f=1;f<=n;f++){
if(closest[f]!=0){
rt[f]=(lt[f]+rt[f])/2;
special[f]=closest[f];
}else{
lt[f]=(lt[f]+rt[f])/2;
}
}
}
bcc.reset();
for(int i=1;i<=m;i++){
if(bcc.root(e[i].from)==bcc.root(e[i].to))continue;
tree[e[i].from].push_back(e[i].to);
tree[e[i].to].push_back(e[i].from);
bcc.mergev(e[i].from,e[i].to);
treeedge[i]=true;
}
dfs(1,0);
bcc.reset();
for(int i=1;i<=m;i++){
if(treeedge[i])continue;
int x=bcc.root(e[i].from),y=bcc.root(e[i].to);
while(!subtree(bcc.topv[x],bcc.topv[y])){
bcc.mergev(x,bcc.root(parent[bcc.topv[x]]));
x=bcc.root(x);
bcc.tim--;
}
while(bcc.root(x)!=bcc.root(y)){
bcc.mergev(y,bcc.root(parent[bcc.topv[y]]));
y=bcc.root(y);
bcc.tim--;
}
bcc.tim++;
edges.push_back(e[i].cost);
}
}
int getMinimumFuelCapacity(int X, int Y){
X++; Y++;
int ans=inf;
if(rt[X]<=m){
ans=e[max(rt[X],rt[Y])].cost;
}
int l=0,r=edges.size()+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(bcc.pastroot(X,tt)==bcc.pastroot(Y,tt)){
r=tt;
}else{
l=tt;
}
}
if(r!=edges.size()+1)ans=min(ans,edges[r-1]);
l=0; r=m+1;
while(l+1<r){
tt=(l+r)/2;
if(graph.pastroot(X,tt)==graph.pastroot(Y,tt)){
r=tt;
}else{
l=tt;
}
}
ans=max(ans,e[r].cost);
return ans;
}
/*
int main(){
init(5,5,{0,1,2,3,4},{1,2,3,4,0},{1,2,3,4,5});
cout<<getMinimumFuelCapacity(0,2)<<"\n";
cout<<getMinimumFuelCapacity(1,3)<<"\n";
cout<<getMinimumFuelCapacity(3,4)<<"\n";
}
*/
Compilation message
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:203:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | if(r!=edges.size()+1)ans=min(ans,edges[r-1]);
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
