| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 645528 | fdnfksd | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll maxN=6e5+10;
#define taskname "codeforce"
ll dp1[maxN],dp2[maxN],mn1[maxN],mn2[maxN];
const ll inf=1e15;
#define pli pair<ll,ll>
#define fi first
#define se second
vector<pli>g[maxN];
vector<pli>c[maxN];
ll vt[maxN];
void dfs1(ll u,ll p)
{
dp1[u]=inf;
mn1[u]=mn2[u]=inf;
for(auto vv:c[u])
{
ll v=vv.fi;
ll w=vv.se;
//if(v==p) {continue;}
dfs1(v,u);
dp1[u]=min(dp1[v]+w,dp1[u]);
if(dp1[v]+w<=mn1[u])
{
mn2[u]=mn1[u];
mn1[u]=dp1[v]+w;
}
else if(dp1[v]+w<=mn2[u])
{
mn2[u]=dp1[v]+w;
}
}
if(vt[u]>=2) dp1[u]=0;
}
void dfs2(ll u,ll p,ll w)
{
dp2[u]=inf;
if(vt[u]>=2) dp2[u]=0;
if(p!=0)
{
if(vt[p]>=2) dp2[u]=w;
else
{
if(dp1[u]+w==mn1[p]) dp2[u]=mn2[p]+w;
else dp2[u]=mn1[p]+w;
dp2[u]=min(dp2[u],dp2[p]+w);
}
}
for(auto vv:c[u])
{
ll v=vv.fi;
ll w=vv.se;
//if(v==p) continue;
dfs2(v,u,w);
}
}
#define pb push_back
ll in[maxN],out[maxN];
bool cmp(ll x,ll y)
{
return in[x]<in[y];
}
ll cnt[maxN];
ll h[maxN];
ll dd[maxN],tg=0;
ll par[maxN][21];
void dfs(ll u=1,ll p=1)
{
in[u]=++tg;
par[u][0]=p;
for(ll i=1;i<=20;i++) par[u][i]=par[par[u][i-1]][i-1];
for(auto vv:g[u])
{
ll v=vv.fi;
ll w=vv.se;
if(v!=p)
{
h[v]=h[u]+1;
dd[v]=dd[u]+w;
dfs(v,u);
}
}
out[u]=tg;
}
ll LCA(ll u, ll v)
{
if(h[u]<h[v]) swap(u,v);
ll log=log2(h[u])+1;
for(ll i=log;i>=0;i--)
{
if(h[par[u][i]]>=h[v]) u=par[u][i];
}
if(u==v) return u;
for(ll i=log;i>=0;i--)
{
if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
}
return par[u][0];
}
ll dis(ll u,ll v)
{
return dd[u]+dd[v]-2*dd[LCA(u,v)];
}
bool isParent(ll x,ll y)
{
return in[x]<=in[y]&&out[y]<=out[x];
}
void Init(ll N,ll A[],ll B[],ll D[])
{
for(ll i=0;i<N-1;i++)
{
g[A[i]].pb({B[i],D[i]});
g[B[i]].pb({A[i],D[i]});
}
dfs();
}
ll Query(ll s,ll x[],ll t,ll y[])
{
vector<ll> vv;
for(ll i=0;i<s;i++) vv.pb(x[i]),vt[x[i]]+=1;
for(ll i=0;i<t;i++) vv.pb(y[i]),vt[y[i]]+=2;
sort(vv.begin(),vv.end(),cmp);
ll k=vv.size();
for(ll i=1;i<k;i++)
{
ll v=LCA(vv[i],vv[i-1]);
vv.pb(v);
}
sort(vv.begin(),vv.end(),cmp);
stack<ll>st;
for(ll i=0;i<vv.size();i++)
{
if(cnt[vv[i]]==0)
{
while(!st.empty()&&(!isParent(st.top(),vv[i]))) st.pop();
if(!st.empty()) c[st.top()].pb({vv[i],dis(st.top(),vv[i])});
st.push(vv[i]);
cnt[vv[i]]=1;
}
}
//cout << '\n';
dfs1(vv[0],0);
dfs2(vv[0],0,0);
ll ans=inf;
for(ll i=0;i<vv.size();i++)
{
if(vt[vv[i]]==1||vt[vv[i]]==3)
{
ans=min(ans,min(dp1[vv[i]],dp2[vv[i]]));
}
}
for(ll i=0;i<vv.size();i++)
{
cnt[vv[i]]=0;
c[vv[i]].clear();
vt[vv[i]]=0;
}
return ans;
}