Submission #240098

#	Time	Username	Problem	Language	Result	Execution time	Memory
240098		frodakcin	Factories (JOI14_factories)	C++11	100 / 100	2998 ms	194908 KiB

factories

#include "factories.h"

#include <cstdio>
#define NDEBUG
#include <cassert>
#include <cstring>
#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 ll 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;
}

Compilation message (stderr)

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:59:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   for(int j=0;i+(1<<j+1)<=N*2-1;++j)
                     ~^~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:95:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<n.size();++i)
              ~^~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67