| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 240096 | frodakcin | Factories (JOI14_factories) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "factories.h"
#include <cstdio>
//#define NDEBUG
#include <cassert>
#include <vector>
#include <algorithm>
#include <functional>
#include <stack>
template<typename T> bool ckmax(T& a, T b){return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b){return b<a?a=b,1:0;}
using ll = long long;
const int MN = 5e5+10;
const int INF = 0x3f3f3f3f3f3f3f3f;
struct edge{public: int n, w;};
struct edge2{public: int n; ll w;};
std::vector<edge> a[MN];
std::vector<edge2> b[MN];
std::vector<int> n;
std::stack<int> stk;
int q[MN*2][20], d[MN], p[MN], ctr, pre[MN], post[MN], c[MN];
ll l[MN], ans, bs[MN], bt[MN];
const auto cmpq = [](int a, int b){return d[a]<d[b];};
void dfs(int n)
{
pre[n] = ctr++, post[n]=pre[n];
q[pre[n]][0] = n;
for(auto x:a[n])
{
if(p[n]==x.n) continue;
d[x.n]=d[n]+1, l[x.n]=l[n]+x.w;
p[x.n] = n;
dfs(x.n);
post[n] = ctr++;
q[post[n]][0] = n;
}
}
int lca(int a, int b)
{
if(a==b) return a;
a=pre[a], b=pre[b];
assert(a!=b);
if(b<a) std::swap(a,b);//++b doesn't matter even though it is technically correct!! (ONLY) On a tree, the last element in the range can be IGNORED
int d=31-__builtin_clz(b-a);
return std::min(q[a][d], q[b-(1<<d)][d], cmpq);
}
void Init(int N, int A[], int B[], int D[])
{
for(int i=0;i<N-1;++i)
a[A[i]].push_back({B[i], D[i]}), a[B[i]].push_back({A[i], D[i]});
d[0]=-1; dfs(0);
assert(ctr == N*2-1);
for(int i=N*2-2;i>=0;--i)
for(int j=0;i+(1<<j+1)<=N*2-1;++j)
q[i][j+1] = std::min(q[i][j], q[i+(1<<j)][j], cmpq);
//printf("%d\n%d\n%d\n%d\n%d\n%d\n", lca(4, 1), lca(3, 5), lca(3, 6), lca(5, 6), lca(0, 4), lca(3, 3));
//1, 2, 1, 1, 0, 3
memset(c, -1, N*sizeof*c);
memset(bs, 0x3f, sizeof bs);
memset(bt, 0x3f, sizeof bt);
}
const auto cmppre = [](int x, int y){return pre[x]<pre[y];};
inline bool anc(int p, int n){return pre[p] <= pre[n] && post[n] <= post[p];}
void dfs2(int n, int p=-1)
{
if(c[n]==0) bs[n]=0;
if(c[n]==1) bt[n]=0;
for(auto x:b[n])
{
if(x.n==p) continue;
dfs2(x.n, n);
ckmin(bs[n], bs[x.n]+x.w);
ckmin(bt[n], bt[x.n]+x.w);
}
ckmin(ans, bs[n]+bt[n]);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0;i<S;++i) n.push_back(X[i]), c[X[i]]=0;
for(int i=0;i<T;++i) n.push_back(Y[i]), c[Y[i]]=1;
std::sort(n.begin(), n.end(), cmppre);
for(int i=0,j=n.size()-1;i<j;++i)
n.push_back(lca(n[i], n[i+1]));
std::sort(n.begin(), n.end(), cmppre);
n.resize(std::distance(n.begin(), std::unique(n.begin(), n.end())));
//build virtual tree
int root=n[0];
stk.push(root);
for(int i=1;i<n.size();++i)
{
while(!anc(stk.top(), n[i]))
stk.pop();
b[stk.top()].push_back({n[i], l[n[i]]-l[stk.top()]});
stk.push(n[i]);
}
//solve on virtual tree
ans=INF;
dfs2(root);
//reset
for(auto x:n) b[x].clear(), bs[x]=bt[x]=INF;
n.clear();
for(int i=0;i<S;++i) c[X[i]]=-1;
for(int i=0;i<T;++i) c[Y[i]]=-1;
return ans;
}