| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 364563 | eric_xiao | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pii pair<ll,ll>
#define ff first
#define ss second
using namespace std;
int pre[500009],td[500009],fst[500009];
ll dep[500009],inv[500009];
int st[21][1500009],cnt = 0;
vector<int> G[500009],d[500009];
vector<int> G2[500009];
vector<ll> d2[500009];
vector<int> ov;
void DFS(int u,int p)
{
cnt++;
pre[u] = cnt;
inv[pre[u]] = u;
fst[u] = ov.size();
ov.push_back(pre[u]);
for(int i = 0;i < G[u].size();i++)
{
int v = G[u][i];
if(v == p) continue;
dep[v] = dep[u] + d[u][i];
td[v] = td[u] + 1;
DFS(v,u);
ov.push_back(pre[u]);
}
}
int LCA(int a,int b)
{
if(a == b) return a;
if(a == 0 || b == 0) return 0LL;
if(fst[a] > fst[b]) swap(a,b);
int ret;
int tp = __lg(fst[b]-fst[a]);
//cout << fst[a] << " " << fst[b] << " " << tp << " " << min(st[tp][fst[a]],st[tp][fst[b] - (1<<tp)]) << endl;
return inv[min(st[tp][fst[a]],st[tp][fst[b] - (1<<tp)])];
// ret = min()
}
const bool cmp(const int &a,const int & b)
{
return pre[a] < pre[b];
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0;i < N-1;i++)
{
A[i]++;
B[i]++;
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
d[A[i]].push_back(D[i]);
d[B[i]].push_back(D[i]);
}
td[1] = 1;
ov.push_back(0);
DFS(1,0);
for(int i = 0;i < ov.size();i++)
{
st[0][i] = ov[i];
}
for(int i = 1;i < 21;i++)
{
for(int j = 0;j+(1<<(i-1)) < ov.size();j++)
{
st[i][j] = min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
//cout << st[i][j] << " ";
}
//cout << endl;
}
}
vector<ll> vs;
int temp[500009];
int stk[500009];
ll ans = 10000000000000000;
int s,x[500009],t,y[500009];
void add_edge(int a,int b)
{
ll tp = abs(dep[a]-dep[b]);
//cerr << a << "_" << b << "_" << tp << endl;
G2[a].push_back(b);
G2[b].push_back(a);
d2[a].push_back(tp);
d2[b].push_back(tp);
}
bool iss[500009],ist[500009];
ll dp1[500009],dp2[500009];
//bool used[500009];
//vector<ll> us;
void DFS2(int u,int p)
{
if(iss[u]) dp1[u] = 0;
if(ist[u]) dp2[u] = 0;
for(int i = 0;i < G2[u].size();i++)
{
int v = G2[u][i];
if(v == p) continue;
DFS2(v,u);
dp1[u] = min(dp1[v]+d2[u][i],dp1[u]);
dp2[u] = min(dp2[v]+d2[u][i],dp2[u]);
}
//cout << u << "_" << dp1[u] << "_" << dp2[u] << endl;
ans = min(ans,dp1[u] + dp2[u]);
}
void DKS()
{
int i;
for(i = 0;i < s;i++)
{
iss[x[i]] = 1;
}
for(i = 0;i < t;i++)
{
ist[y[i]] = 1;
}/*
for(auto tt : us)
{
dp1[tt] = dp2[tt] = 10000000000000000;
}*/
for(i = 0;i <= 5000;i++) dp1[i] = dp2[i] = 10000000000000000;
DFS2(x[0],0);
for(i = 0;i < s;i++)
{
iss[x[i]] = 0;
}
for(i = 0;i < t;i++)
{
ist[y[i]] = 0;
}
}
long long Query(int S, int X[], int T, int Y[]) {
vs.clear();
s = S;
us.clear();
for(int i = 0;i < S;i++)
{
X[i]++;
//used[X[i]] = 1;
//us.push_back(X[i]);
x[i] = X[i];
G2[X[i]].clear();
d2[X[i]].clear();
temp[X[i]] = 1;
vs.push_back(X[i]);
}
int fg = 0;
t = T;
for(int i = 0;i < T;i++)
{
Y[i]++;
y[i] = Y[i];
G2[Y[i]].clear();
d2[Y[i]].clear();
vs.push_back(Y[i]);
//if(used[Y[i]] == 0)us.push_back(Y[i]);
//used[Y[i]] = 1;
if(temp[Y[i]] == 1) fg = 1;
}
for(int i = 0;i < S;i++)
{
temp[X[i]] = 0;
}
if(fg == 1)
{
//for(int i = 0;i < S;i++) used[X[i]] = 0;
//for(int i = 0;i < T;i++) used[Y[i]] = 0;
return 0;
}
sort(vs.begin(),vs.end(),cmp);
stk[0] = 0;
int sz = 1;
ans = 10000000000000000;
for(int i = 0;i < vs.size();i++)
{
ll u = vs[i];
ll p = LCA(u,stk[sz-1]);
//cerr << vs[i] << " p = " << p << endl;
/*if(used[p] == 0)
{
used[p] = 1;
//us.push_back(p);
G2[p].clear();
d2[p].clear();
}*/
if(p == stk[sz-1]) stk[sz++] = u;
else
{
while(sz > 1 && td[stk[sz-2]] >= td[p])
{
add_edge(stk[sz-1],stk[sz-2]);
sz--;
}
if(stk[sz-1] != p)
{
add_edge(stk[sz-1],p);
stk[sz-1] = p;
}
stk[sz++] = u;
}
}
for (int i = 1; i < sz - 1; ++i) add_edge(stk[i], stk[i + 1]);
DKS();
//for(int i = 0;i < S;i++) used[X[i]] = 0;
//for(int i = 0;i < T;i++) used[Y[i]] = 0;
return ans;
}