#include<bits/stdc++.h>
#include"swap.h"
#define taskname "vcl"
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
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=1e6+1;
const int INF=1e9+7;
const int mod=1e9+7;
int n,m,d[maxn],cnt[maxn],par[maxn],h[maxn],up[maxn][20],f[maxn][20],g[maxn][20],laz[maxn][20];
struct edge
{
int u,v,w,used;
}e[maxn];
vector<int> adj[maxn];
bool operator <(edge a,edge b)
{
return a.w<b.w;
}
int fp(int x)
{
if(par[x]<0) return x;
return par[x]=fp(par[x]);
}
void uni(int a,int b)
{
a=fp(a);
b=fp(b);
if(a==b) return;
if(par[a]>par[b]) swap(a,b);
par[a]+=par[b];
par[b]=a;
}
void dfs(int x,int par)
{
h[x]=h[par]+1;
up[x][0]=par;
for(int i:adj[x])
{
int y=e[i].u+e[i].v-x;
if(y==par) continue;
f[y][0]=e[i].w;
dfs(y,x);
}
}
struct ele
{
int des,dis;
};
bool operator <(ele a,ele b)
{
return a.dis>b.dis;
}
void dijkstra()
{
priority_queue<ele> pq;
for(int i=1;i<=n;i++)
{
pq.push({i,d[i]});
cnt[i]=0;
}
while(!pq.empty())
{
int des=pq.top().des;
int dis=pq.top().dis;
pq.pop();
if(cnt[des]) continue;
cnt[des]=1;
d[des]=dis;
for(int i:adj[des])
{
int des1=e[i].u+e[i].v-des;
pq.push({des1,max(dis,e[i].w)});
}
}
for(int i=1;i<=n;i++)
{
g[i][0]=d[i];
}
}
void update(int x,int y,int w)
{
if(h[x]!=h[y])
{
if(h[x]<h[y]) swap(x,y);
int dif=h[x]-h[y];
for(int i=0;i<20;i++)
{
if(dif&(1<<i))
{
laz[x][i]=min(laz[x][i],w);
x=up[x][i];
}
}
}
if(x!=y)
{
int lg=__lg(h[x]);
for(int i=lg;i>=0;i--)
{
if(up[x][i]!=up[y][i])
{
laz[x][i]=min(laz[x][i],w);
laz[y][i]=min(laz[y][i],w);
x=up[x][i];
y=up[y][i];
}
}
laz[x][0]=min(laz[x][0],w);
laz[y][0]=min(laz[y][0],w);
x=up[x][0];
}
laz[x][0]=min(laz[x][0],w);
}
void init(int _n,int _m,vector<int> _u,vector<int> _v,vector<int> _w)
{
n=_n;
m=_m;
for(int i=0;i<m;i++)
{
e[i+1].u=++_u[i];
e[i+1].v=++_v[i];
e[i+1].w=_w[i];
e[i+1].used=0;
}
sort(e+1,e+m+1);
for(int i=1;i<=n;i++)
{
d[i]=INF;
par[i]=-1;
}
for(int i=1;i<=m;i++)
{
if(++cnt[e[i].u]==3) d[e[i].u]=e[i].w;
if(++cnt[e[i].v]==3) d[e[i].v]=e[i].w;
if(fp(e[i].u)!=fp(e[i].v))
{
uni(e[i].u,e[i].v);
adj[e[i].u].push_back(i);
adj[e[i].v].push_back(i);
e[i].used=1;
}
}
dfs(1,0);
dijkstra();
for(int i=1;i<=n;i++)
{
for(int j=0;j<20;j++)
{
laz[i][j]=INF;
}
}
for(int j=1;j<20;j++)
{
for(int i=1;i<=n;i++)
{
up[i][j]=up[up[i][j-1]][j-1];
}
}
for(int i=1;i<=m;i++)
{
if(e[i].used==0)
{
update(e[i].u,e[i].v,e[i].w);
}
}
for(int j=1;j<20;j++)
{
for(int i=1;i<=n;i++)
{
f[i][j]=max(f[i][j-1],f[up[i][j-1]][j-1]);
g[i][j]=min(g[i][j-1],g[up[i][j-1]][j-1]);
}
}
for(int j=19;j;j--)
{
for(int i=1;i<=n;i++)
{
laz[i][j-1]=min(laz[i][j-1],laz[i][j]);
laz[up[i][j-1]][j-1]=min(laz[up[i][j-1]][j-1],laz[i][j]);
}
}
}
int getMinimumFuelCapacity(int x,int y)
{
int w1=0,w2=INF;
if(h[x]!=h[y])
{
if(h[x]<h[y]) swap(x,y);
int dif=h[x]-h[y];
for(int i=0;i<20;i++)
{
if(dif&(1<<i))
{
w1=max(w1,f[x][i]);
w2=min(w2,g[x][i]);
x=up[x][i];
}
}
}
if(x!=y)
{
int lg=__lg(h[x]);
for(int i=lg;i>=0;i--)
{
if(up[x][i]!=up[y][i])
{
w1=max(w1,f[x][i]);
w2=min(w2,g[x][i]);
w1=max(w1,f[y][i]);
w2=min(w2,g[y][i]);
x=up[x][i];
y=up[y][i];
}
}
w1=max(w1,f[x][0]);
w1=max(w1,f[y][0]);
w2=min(w2,g[x][0]);
w2=min(w2,g[y][0]);
x=up[x][0];
}
w2=min(w2,g[x][0]);
int ans=max(w1,min(w2,laz[x][0]));
if(ans==INF) return -1;
else return ans;
}
//signed main()
//{
// if (fopen(taskname".INP","r"))
// {
// freopen(taskname".INP","r",stdin);
// freopen(taskname"1.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";
// }
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
