#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "swap.h"
int n,m;
int val=0;
vector<pair<int,pair<int,int>>> ed;
int par[100001];
int ss[100001];
int tt[100001];
int dd[100001];
multiset<int> xx[100001];
vector<int> comp[100001];
int ans[100001];
int find(int no){
if(par[no]==no){
return no;
}
par[no]=find(par[no]);
return par[no];
}
void upd(int x,int y){
int stt=0;
if(ss[x]>tt[x]-1){
stt=1;
}
auto ee=xx[x].end();
ee--;
if(*ee>=3){
stt=1;
}
if(stt){
for(auto j:comp[x]){
if(ans[j]==-1){
ans[j]=y;
}
}
}
}
int par2[100001];
int find2(int no){
if(par2[no]==no){
return no;
}
par2[no]=find2(par2[no]);
return par2[no];
}
vector<pair<int,int>> adj[100001];
int par3[100001][20];
int mi[100001][20];
int lev[100001];
int dfs(int no,int parr=-1,int levv=0){
lev[no]=levv;
par3[no][0]=parr;
// cout<<no<<":"<<endl;
for(auto j:adj[no]){
if(j.a==parr){
continue;
}
// cout<<no<<":"<<j.a<<endl;
mi[j.a][0]=j.b;
dfs(j.a,no,levv+1);
}
}
void init(int nn, int mm,vector<int> aa,vector<int> bb,vector<int> cc) {
m=mm;
n=nn;
for(int i=0;i<m;i++){
ed.pb({cc[i],{aa[i],bb[i]}});
}
sort(ed.begin(),ed.end());
for(int i=0;i<n;i++){
par[i]=i;
ss[i]=0;
dd[i]=0;
xx[i].clear();
tt[i]=1;
xx[i].insert(0);
ans[i]=-1;
adj[i].clear();
comp[i].pb(i);
}
for(auto j:ed){
int x=find(j.b.a);
int y=find(j.b.b);
if(x==y){
ss[x]+=1;
auto jj=xx[x].find(dd[j.b.a]);
xx[x].erase(jj);
dd[j.b.a]+=1;
xx[x].insert(dd[j.b.a]);
jj=xx[x].find(dd[j.b.b]);
xx[x].erase(jj);
dd[j.b.b]+=1;
xx[x].insert(dd[j.b.b]);
if(ans[x]==-1){
upd(x,j.a);
}
}
else{
if(xx[x].size()<xx[y].size()){
swap(x,y);
}
par[y]=x;
for(auto jj:xx[y]){
xx[x].insert(jj);
}
for(auto jj:comp[y]){
comp[x].pb(jj);
if(ans[x]!=-1 and ans[jj]==-1){
ans[jj]=j.a;
}
}
comp[y].clear();
xx[y].clear();
ss[x]+=ss[y]+1;
tt[x]+=tt[y];
auto jj=xx[x].find(dd[j.b.a]);
xx[x].erase(jj);
dd[j.b.a]+=1;
xx[x].insert(dd[j.b.a]);
jj=xx[x].find(dd[j.b.b]);
xx[x].erase(jj);
dd[j.b.b]+=1;
xx[x].insert(dd[j.b.b]);
if(ans[x]==-1){
upd(x,j.a);
}
}
}
/*for(int i=0;i<n;i++){
cout<<ans[i]<<":";
}
cout<<endl;*/
for(int i=0;i<n;i++){
par2[i]=i;
}
for(auto j:ed){
int xx=find2(j.b.b);
int yy=find2(j.b.a);
if(xx!=yy){
par2[xx]=yy;
// cout<<xx<<" "<<yy<<endl;
adj[j.b.a].pb({j.b.b,j.a});
adj[j.b.b].pb({j.b.a,j.a});
// cout<<j.b.a<<","<<j.b.b<<endl;
}
}
dfs(0);
for(int j=1;j<20;j++){
for(int i=0;i<n;i++){
if(par3[i][j-1]==-1){
par3[i][j]=-1;
continue;
}
par3[i][j]=par3[par3[i][j-1]][j-1];
if(par3[i][j]!=-1){
mi[i][j]=max(mi[i][j-1],mi[par3[i][j-1]][j-1]);
}
}
}
}
int getMinimumFuelCapacity(int ac, int bc) {
int aa=ac;
int bb=bc;
if(ans[aa]==-1 or ans[bb]==-1){
return -1;
}
int tot=max(ans[aa],ans[bb]);
if(lev[aa]>lev[bb]){
swap(aa,bb);
}
int dif=lev[bb]-lev[aa];
for(int j=0;j<19;j++){
if((1<<j)&dif){
tot=max(tot,mi[bb][j]);
bb=par3[bb][j];
}
}
if(bb==aa){
return tot;
}
for(int j=19;j>=0;j--){
if(par3[aa][j]!=par3[bb][j]){
tot=max(tot,max(mi[aa][j],mi[bb][j]));
aa=par3[aa][j];
bb=par3[bb][j];
}
}
tot=max(tot,max(mi[aa][0],mi[bb][0]));
return tot;
//return ac;
}
Compilation message
swap.cpp: In function 'int dfs(int, int, int)':
swap.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
76 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
19564 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
19564 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
19564 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
