#include<bits/stdc++.h>
#include"swap.h"
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int long long
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e5+6;
const int INF=1e9+1;
struct edge
{
int u,v,w,used;
}e[maxn];
bool operator <(edge a,edge b)
{
return a.w<b.w;
}
vector<int> adj[maxn];
vector<int> gg[maxn];
int up[maxn][20],f[maxn][20],g[maxn][20],n,m,par[maxn],h[maxn],v[maxn],d[maxn],vis[maxn];
int fp(int x)
{
if(par[x]<0) return x;
return par[x]=fp(par[x]);
}
void uni(int a,int b,int i)
{
a=fp(a);
b=fp(b);
if(a==b) return;
e[i].used=1;
if(par[a]>par[b]) swap(a,b);
par[a]+=par[b];
par[b]=a;
}
void dfs(int x,int par)
{
up[x][0]=par;
h[x]=h[par]+1;
for(int i:adj[x])
{
if(e[i].used==0) continue;
int y=e[i].u+e[i].v-x;
if(y==par) continue;
f[y][0]=e[i].w;
dfs(y,x);
}
}
int lca(int a,int b)
{
if(h[a]<h[b]) swap(a,b);
if(h[a]!=h[b])
{
int dif=h[a]-h[b];
for(int i=0;i<20;i++)
{
if(dif&(1<<i)) a=up[a][i];
}
}
if(a==b) return a;
else
{
int lg=__lg(h[b]);
for(int i=lg;i>=0;i--)
{
if(up[a][i]!=up[b][i])
{
a=up[a][i];
b=up[b][i];
}
}
return up[a][0];
}
}
int findf(int x,int w)
{
int ans=0;
for(int i=0;i<20;i++)
{
if(w&(1<<i))
{
ans=max(ans,f[x][i]);
x=up[x][i];
}
}
return ans;
}
int findg(int x,int w)
{
int ans=INF;
for(int i=0;i<20;i++)
{
if(w&(1<<i))
{
ans=min(ans,g[x][i]);
x=up[x][i];
}
}
return ans;
}
void updg(int x,int w,int val)
{
for(int i=0;i<20;i++)
{
if(w&(1<<i))
{
g[x][i]=min(g[x][i],val);
x=up[x][i];
}
}
}
void upd(int a,int b,int val)
{
int p=lca(a,b);
int wa=findf(a,h[a]-h[p]);
int wb=findf(b,h[b]-h[p]);
val=max({wb,wa,val});
updg(a,h[a]-h[p],val);
updg(b,h[b]-h[p],val);
}
void dijkstra()
{
priority_queue<pii> pq;
for(int i=1;i<=n;i++)
{
vis[i]=0;
pq.push({-v[i],i});
}
while(!pq.empty())
{
int x=pq.top().sc;
int dis=-pq.top().fi;
pq.pop();
if(vis[x]) continue;
vis[x]=1;
d[x]=dis;
for(int i:gg[x])
{
int y=e[i].u+e[i].v-x;
pq.push({-max(dis,e[i].w),i});
}
}
for(int i=1;i<=n;i++)
{
v[i]=d[i];
}
}
void init(int n_,int m_,vector<int> u_,vector<int> v_,vector<int> w_)
{
n=n_;
m=m_;
for(int i=0;i<(int) u_.size();i++)
{
e[i+1]={u_[i]+1,v_[i]+1,w_[i],0};
}
sort(e+1,e+m+1);
for(int i=1;i<=n;i++)
{
par[i]=-1;
}
for(int i=1;i<=m;i++)
{
uni(e[i].u,e[i].v,i);
if(e[i].used==1)
{
adj[e[i].u].push_back(i);
adj[e[i].v].push_back(i);
}
gg[e[i].u].push_back(i);
gg[e[i].v].push_back(i);
}
dfs(1,0);
for(int i=1;i<=n;i++)
{
for(int j=0;j<20;j++)
{
g[i][j]=INF;
}
v[i]=INF;
}
for(int i=1;i<20;i++)
{
for(int j=1;j<=n;j++)
{
up[j][i]=up[up[j][i-1]][i-1];
f[j][i]=max(f[j][i-1],f[up[j][i-1]][i-1]);
}
}
for(int i=1;i<=m;i++)
{
if(e[i].used==0)
{
upd(e[i].u,e[i].v,e[i].w);
}
}
for(int i=3;i;i--)
{
for(int j=1;j<=n;j++)
{
g[j][i-1]=min(g[j][i-1],g[j][i]);
g[up[j][i-1]][i-1]=min(g[up[j][i-1]][i-1],g[j][i]);
// cout<<g[j][i]<<" ";
}
// cout<<"\n";
}
for(int i=1;i<=n;i++)
{
v[i]=min(v[i],g[i][0]);
v[up[i][0]]=min(v[up[i][0]],g[i][0]);
}
dijkstra();
for(int i=1;i<=n;i++)
{
for(int j=0;j<20;j++)
{
g[i][j]=INF;
}
}
for(int i=1;i<=n;i++)
{
g[i][0]=min(v[i],v[up[i][0]]);
}
for(int i=1;i<20;i++)
{
for(int j=1;j<=n;j++)
{
g[j][i]=min(g[j][i-1],g[up[j][i-1]][i-1]);
}
}
}
int getMinimumFuelCapacity(int a,int b)
{
int p=lca(a,b);
int wa=findf(a,h[a]-h[p]);
int wb=findf(b,h[b]-h[p]);
int wwa=findg(a,h[a]-h[p]);
int wwb=findg(b,h[b]-h[p]);
int lmao=min(wwa,wwb);
if(lmao==INF) return -1;
return max({wa,wb,lmao});
}
//signed main()
//{
// if (fopen(taskname".INP","r"))
// {
// freopen(taskname".INP","r",stdin);
// freopen(taskname".OUT","w",stdout);
// }
// Faster
// int n,m,q;
// vector<int> v1,v2,v3;
// cin>>n>>m>>q;
// for(int i=1;i<=m;i++)
// {
// int u,v,w;
// cin>>u>>v>>w;
// v1.push_back(u);
// v2.push_back(v);
// v3.push_back(w);
// }
// init(n,m,v1,v2,v3);
// while(q--)
// {
// int u,v;
// cin>>u>>v;
// cout<<getMinimumFuelCapacity(++u,++v)<<"\n";
// }
// for(int i=1;i<=n;i++)
// {
// for(int j=0;j<=1;j++)
// {
// cout<<g[i][j]<<" ";
// }
// cout<<"\n";
// }
// for(int i=1;i<=n;i++) cout<<v[i]<<" ";
//}
Compilation message
swap.cpp: In function 'void dijkstra()':
swap.cpp:147:17: warning: unused variable 'y' [-Wunused-variable]
147 | int y=e[i].u+e[i].v-x;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
20824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
20824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
20824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
20824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
20824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
20824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
