| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 918728 | User0069 | 자매 도시 (APIO20_swap) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.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];
int up[maxn][20],f[maxn][20],g[maxn][20],n,m,par[maxn],h[maxn],v[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=0;
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 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);
}
}
dfs(1,0);
memset(g,INF,sizeof g);
memset(v,INF,sizeof v);
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=19;i;i--)
{
for(int j=1;j<=n;j++)
{
g[j][i-1]=min(g[j][i-1],g[i][j]);
g[up[j][i-1]][i-1]=min(g[up[j][i-1]][i-1],g[i][j]);
}
}
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]);
}
memset(g,INF,sizeof g);
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]);
return max({wa,wb,min(wwa,wwb)});
}
//signed main()
//{
// if (fopen(taskname".INP","r"))
// {
// freopen(taskname".INP","r",stdin);
// freopen(taskname".OUT","w",stdout);
// }
// Faster
//}