| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 362099 | denkendoemeer | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool maxi(ll &a,ll b)
{
if (a<b)
return a=b,1;
return 0;
}
bool mini(ll &a,ll b)
{
if (a>b)
return a=b,1;
return 0;
}
struct ed
{
int to,w;
};
vector<ed>e[500005];
struct grup
{
int c;
ll d;
};
vector<grup>g[500005];
int sum[500005],ok[500005];
ll ans,b1[500005],b2[500005];
int dfs(int nod,int t=-1)
{
sum[nod]=1;
for(auto it:e[nod])
if (ok[it.to]==0 && it.to!=t)
sum[nod]+=dfs(it.to,nod);
return sum[nod];
}
int centr(int nod,int aux,int t=-1)
{
for(auto it:e[nod])
if (ok[it.to]==0 && it.to!=t)
if (sum[it.to]*2>=aux)
return centr(it.to,aux,nod);
return nod;
}
int auxi;
void dfs2(int nod,int t=-1,ll dist=0)
{
g[nod].push_back({auxi,dist});
for(auto it:e[nod])
if (ok[it.to]==0 && it.to!=t)
dfs2(it.to,nod,dist+it.w);
}
void calc(int nod)
{
int c=centr(nod,dfs(nod));
auxi=c;
dfs2(c);
ok[c]=1;
for(auto it:e[c])
if (ok[it.to]==0)
calc(it.to);
}
void Init(int n,int a[],int b[],int d[])
{
int i;
for(i=0;i<n-1;i++)
e[a[i]].push_back({b[i],d[i]}),e[b[i]].push_back({a[i],d[i]});
calc(0);
memset(b1,0x3f,sizeof(b1));
memset(b2,0x3f,sizeof(b2));
}
ll query(int s,int x[],int t,int y[])
{
ans=2e17;
int i;
for(i=0;i<s;i++)
for(auto it:g[x[i]])
mini(b2[it.c],it.d);
for(i=0;i<t;i++)
for(auto it:g[y[i]]){
mini(b1[it.c],it.d);
mini(ans,b1[it.c]+b2[it.c]);
}
for(i=0;i<s;i++)
for(auto it:g[x[i]])
b1[it.c]=b2[it.c]=2e17;
for(i=0;i<t;i++)
for(auto it:g[y[i]])
b1[it.c]=b2[it.c]=2e17;
return ans;
}