| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 310665 | vipghn2003 | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=5e5+5;
int n,m,p[N][21],level[N],up[N],sz[N];
long long mn[N],dep[N];
bool vis[N];
vector<pii>adj[N];
void dfs(int x,int par=-1)
{
for(int k=1;k<=20;k++) p[x][k]=p[p[x][k-1]][k-1];
for(auto&u:adj[x])
{
if(u.fi==par) continue;
p[u.fi][0]=x;
dep[u.fi]=dep[x]+u.se;
level[u.fi]=level[x]+1;
dfs(u.fi,x);
}
}
int lca(int x,int y)
{
if(level[x]>level[y]) swap(x,y);
int diff=level[y]-level[x];
for(int k=20;k>=0;k--) if(diff>>k&1) y=p[y][k];
if (x==y) return x;
for(int k=20;k>=0;k--)
{
if (p[x][k]!=p[y][k])
{
x=p[x][k];
y=p[y][k];
}
}
return p[x][0];
}
long long dist(int u,int v)
{
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void findsz(int u,int p=-1)
{
sz[u]=1;
for(auto&v:adj[u])
{
if (v.fi!=p&&!vis[v.fi])
{
findsz(v.fi,u);
sz[u]+=sz[v.fi];
}
}
}
int find_cen(int u,int p,int m)
{
for(auto&v:adj[u])
{
if(v.fi!=p&&!vis[v.fi])
{
if (sz[v.fi]>m/2) return find_cen(v.fi,u,m);
}
}
return u;
}
void centroid(int root=1,int p=-1)
{
findsz(root,root);
int k=find_cen(root,root,sz[root]);
up[k]=p;
vis[k]=true;
for(auto&u:adj[k]) if(!vis[u.fi])centroid(u.fi,k);
}
void init(int N,vector<int>A,vector<int>B,vector<int>D)
{
n=N;
for(int i=1;i<=n;i++) mn[i]=1e18;
m=A.size();
for(int i=0;i<m;i++)
{
int u=A[i];
int v=B[i];
u++,v++;
int w=D[i];
adj[u].push_back(mp(v,w));
adj[v].push_back(mp(u,w));
}
dfs(1);
centroid();
}
long long Query(int S,vector<int>X,int T,vector<int>Y)
{
for(int i=0;i<S;i++) X[i]++;
for(int i=0;i<T;i++)
{
Y[i]++;
int cur=Y[i];
while(cur!=-1)
{
mn[cur]=min(mn[cur],dist(Y[i],cur));
cur=up[cur];
}
}
long long res=1e18;
for(int i=0;i<S;i++)
{
int cur=X[i];
while(cur!=-1)
{
res=min(res,mn[cur]+dist(X[i],cur));
cur=up[cur];
}
}
for(int i=0;i<T;i++)
{
int cur=Y[i];
while(cur!=-1)
{
mn[cur]=1e18;
cur=up[cur];
}
}
return res;
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>q;
vector<int>a(n-1),b(n-1),d(n-1);
for(int i=0;i<n-1;i++) cin>>a[i]>>b[i]>>d[i];
init(n,a,b,d);
while(q--)
{
int s,t;
cin>>s>>t;
vector<int>x(s),y(t);
for(int i=0;i<s;i++) cin>>x[i];
for(int i=0;i<t;i++) cin>>y[i];
cout<<Query(s,x,t,y)<<'\n';
}
}
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
*/