#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 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;
int n,m,f[maxn][20],par[maxn],v[maxn],cnt[maxn];
struct edge
{
int u,v,w,used;
} e[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;
}
struct tree
{
int up[maxn][20],h[maxn],f[maxn][20];
vector<int> adj[maxn];
void dfs(int x,int par,int w)
{
up[x][0]=par;
h[x]=h[par]+1;
f[x][0]=w;
for(int i:adj[x])
{
int y=e[i].u+e[i].v-x;
if(y==par) continue;
dfs(y,x,e[i].w);
}
}
void buildST(bool wow)
{
for(int i=1; i<=n; i++)
{
if(up[i][0]==0) dfs(i,0,INF);
}
if(wow)
{
v[0]=INF;
f[0][0]=-INF;
for(int i=1;i<=n;i++)
{
f[i][0]=-min(v[i],v[up[i][0]]);
}
}
for(int i=1; i<20; i++)
{
for(int j=0; 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]);
}
}
}
int get(int a,int b)
{
int ans=-INF;
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))
{
ans=max(ans,f[a][i]);
a=up[a][i];
}
}
}
if(a==b) return ans;
else
{
for(int i=19;i>=0;i--)
{
if(up[a][i]!=up[b][i])
{
ans=max(ans,f[a][i]);
ans=max(ans,f[b][i]);
a=up[a][i];
b=up[b][i];
// cout<<ans<<"!\n";
}
}
ans=max(ans,f[a][0]);
ans=max(ans,f[b][0]);
// cout<<ans<<"!\n";
return ans;
}
}
} f1,f2,f3;
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++)
{
v[i]=INF;
}
for(int i=1;i<=m;i++)
{
if(++cnt[e[i].u]==3)
{
v[e[i].u]=e[i].w;
}
if(++cnt[e[i].v]==3)
{
v[e[i].v]=e[i].w;
}
}
for(int i=1;i<=n;i++)
{
par[i]=-1;
}
for(int i=1; i<=m; i++)
{
if(fp(e[i].u)!=fp(e[i].v))
{
uni(e[i].u,e[i].v);
f1.adj[e[i].u].push_back(i);
f1.adj[e[i].v].push_back(i);
f3.adj[e[i].u].push_back(i);
f3.adj[e[i].v].push_back(i);
e[i].used=1;
}
}
for(int i=1;i<=n;i++)
{
par[i]=-1;
}
for(int i=1; i<=m; i++)
{
if(e[i].used==0&&fp(e[i].u)!=fp(e[i].v))
{
uni(e[i].u,e[i].v);
f2.adj[e[i].u].push_back(i);
f2.adj[e[i].v].push_back(i);
e[i].used=1;
}
}
f1.buildST(0);
f2.buildST(0);
f3.buildST(1);
}
int getMinimumFuelCapacity(int a,int b)
{
int w1=f1.get(a,b);
int w2=f2.get(a,b);
int w3=f3.get(a,b);
w3=-w3;
return max(min(w2,w3),w1);
}
//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";
// }
//// for(int i=1;i<=n;i++)
//// {
//// cout<<f1.f[i][0]<<"\n";
//// }
//// cout<<f1.get(3,4)<<"\n";
//}
| # |
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 |
- |
