#include "swap.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct A{
int u,v,w;
bool operator < (const A&o) const{
return w<o.w;
}
};
A e[200010];
vector<A> g[100010],g2[100010];
int p[100010],pa[20][100010],mx[20][100010],mark[200010],miout[100010],mi[20][100010],mi2[20][100010],mi3[20][100010],h[100010],cnt;
int fr(int i){
if(p[i]==i) return p[i];
return p[i]=fr(p[i]);
}
void dfs(int i,int prev,int weight){
pa[0][i]=prev;
mx[0][i]=weight;
for(auto x : g[i]){
if(mark[x.v]==0) {
miout[i]=min(miout[i],x.w);
miout[x.u]=min(miout[x.u],x.w);
continue;
}
if(x.u==prev) continue;
h[x.u]=h[i]+1;
dfs(x.u,i,x.w);
g2[i].push_back({x.u,x.v,x.w});
}
}
void init(int N, int M,vector<int> u,vector<int> v,vector<int> w) {
int i,j,pu,pv;
n=N;
m=M;
for(i=0;i<N;i++){
p[i]=i;
}
for(i=0;i<M;i++){
e[i]={u[i],v[i],w[i]};
}
sort(e,e+M);
for(i=0;i<M;i++){
g[e[i].u].push_back({e[i].v,i,e[i].w});
g[e[i].v].push_back({e[i].u,i,e[i].w});
}
for(i=0;i<M;i++){
pu=fr(e[i].u);
pv=fr(e[i].v);
if(pu==pv) continue;
mark[i]=1;
p[pu]=pv;
}
memset(miout,127,sizeof miout);
memset(mi,127,sizeof mi);
memset(mi2,127,sizeof mi2);
memset(mi3,127,sizeof mi3);
memset(h,-1,sizeof h);
memset(pa,-1,sizeof pa);
h[0]=0;
dfs(0,-1,-1);
for(j=0;j<N;j++) sort(g2[i].begin(),g2[i].end()),mi[0][j]=mi2[0][j]=mi3[0][j]=miout[j];
for(j=0;j<N;j++){
if(g2[j].size()>=1){
mi[0][j]=min(mi[0][j],g2[j][0].w);
}
if(g2[j].size()>=2){
mi2[0][j]=min(mi2[0][j],g2[j][1].w);
}
if(g2[j].size()>=3){
mi3[0][j]=min(mi3[0][j],g2[j][2].w);
}
}
for(i=1;i<20;i++){
for(j=1;j<N;j++){
pa[i][j]=pa[i-1][pa[i-1][j]];
mx[i][j]=max(mx[i-1][j],mx[i-1][pa[i-1][j]]);
mi[i][j]=min(mi[i-1][j],mi[i-1][pa[i-1][j]]);
mi2[i][j]=min(mi2[i-1][j],mi2[i-1][pa[i-1][j]]);
mi3[i][j]=min(mi3[i-1][j],mi3[i-1][pa[i-1][j]]);
}
}
}
A LCA(int u,int v){
if(h[u]<h[v]) swap(u,v);
int diff=h[u]-h[v],maxedge=-1,minout=2e9,i;
if(h[u]==h[v]) minout=min(minout,mi[0][v]);
minout=min(minout,mi[0][u]);
for(i=0;i<20;i++){
if((diff&(1<<i))!=0) maxedge=max(mx[i][u],maxedge),minout=min(mi2[i][u],minout),u=pa[i][u];
}
if(u==v) return {u,maxedge,minout};
for(i=19;i>=0;i--){
if(pa[i][u]!=pa[i][v]){
maxedge=max(mx[i][u],maxedge),minout=min(mi2[i][u],minout);
maxedge=max(mx[i][v],maxedge),minout=min(mi2[i][v],minout);
u=pa[i][u];
v=pa[i][v];
}
}
maxedge=max(mx[0][u],maxedge),minout=min(mi2[0][u],minout);
maxedge=max(mx[0][v],maxedge),minout=min(mi2[0][v],minout);
return {pa[0][u],maxedge,minout};
}
int getMinimumFuelCapacity(int X, int Y) {
int i,j,ch=0,u,v;
cnt++;
A all=LCA(X,Y);
int lca=all.u,maxedge=all.v,minout=all.w;
printf("%d %d %d\n",lca,maxedge,minout);
if(max(maxedge,minout)>1e9) return -1;
return max(maxedge,minout);
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
3 2
0 1 5
0 2 5
1
1 2
*/
Compilation message
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:108:9: warning: unused variable 'i' [-Wunused-variable]
108 | int i,j,ch=0,u,v;
| ^
swap.cpp:108:11: warning: unused variable 'j' [-Wunused-variable]
108 | int i,j,ch=0,u,v;
| ^
swap.cpp:108:13: warning: unused variable 'ch' [-Wunused-variable]
108 | int i,j,ch=0,u,v;
| ^~
swap.cpp:108:18: warning: unused variable 'u' [-Wunused-variable]
108 | int i,j,ch=0,u,v;
| ^
swap.cpp:108:20: warning: unused variable 'v' [-Wunused-variable]
108 | int i,j,ch=0,u,v;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
37144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
37144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
37144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
37144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
37144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
37144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
