| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 84353 | Pajaraja | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include <bits/stdc++.h>
#define MAXN 500007
#define MAXL 20
const long long inf=1000000000000000000LL;
using namespace std;
vector<int> g[MAXN];
vector<long long> c[MAXN];
int p[MAXN],n,sz,cn,in[MAXN],gl,arr[MAXN],d[MAXN];
long long be[MAXN][MAXL],opt[MAXN];
bool vc[MAXN];
inline int dfssize(int s,int f)
{
int x=1;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]]) x+=dfssize(g[s][i],s);
return x;
}
inline int dfsc(int s,int f)
{
int x=1;
bool ce=true;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]])
{
int a=dfsc(g[s][i],s);
if(a>sz/2) ce=false;
x+=a;
}
if(sz-x>sz/2) ce=false;
if(ce) cn=s;
return x;
}
inline void dfs(int s,int f,long long dist,int du)
{
be[s][d[s]-du]=dist;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && d[g[s][i]]>=du) dfs(g[s][i],s,dist+c[s][i],po);
}
inline void centrodecomp(int s,int f,int du)
{
sz=dfssize(s,-1);
dfsc(s,-1);
p[cn]=f;
vc[cn]=true;
d[cn]=du;
int tmp=cn;
for(int i=0;i<g[tmp].size();i++) if(!vc[g[tmp][i]]) centrodecomp(g[tmp][i],tmp,du+1);
}
void Init(int N, int A[], int B[], int D[])
{
n=N;
int root;
for(int i=0;i<n-1;i++) {g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); c[A[i]].push_back(D[i]); c[B[i]].push_back(D[i]);}
centrodecomp(0,-1,0);
for(int i=0;i<n;i++) dfs(i,-1,0,d[i]);
fill(opt,opt+MAXN,inf);
}
long long Query(int S, int X[], int T, int Y[])
{
long long sk=inf;
for(int i=0;i<S;i++)
{
int a=X[i];
for(int cnt=0;a!=-1;cnt++) {opt[a]=min(opt[a],be[X[i]][cnt]); a=p[a];}
}
for(int i=0;i<T;i++)
{
int a=Y[i],cnt=0;
for(int cnt=0;a!=-1;cnt++) {if(opt[a]!=inf) sk=min(sk,be[Y[i]][cnt]+opt[a]); a=p[a];}
}
for(int i=0;i<S;i++) while(X[i]!=-1) {opt[X[i]]=inf; X[i]=p[X[i]];}
return sk;
}