Submission #126605

#	Time	Username	Problem	Language	Result	Execution time	Memory
126605		fizzydavid	Factories (JOI14_factories)	C++14	33 / 100	8015 ms	140400 KiB

factories

//by yjz
#include "factories.h"
#include<bits/stdc++.h>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
typedef long long ll;
using namespace std;
const int maxn = 500111;
int n;
vector<pair<int,int> > con[maxn];
int fa[20][maxn], lv[maxn];
ll len[maxn];
int dfn[maxn], dtot;
vector<pair<int,ll> > ncon[maxn];
int type[maxn];
void dfs(int x)
{
	for (int i=1; i<20; i++) fa[i][x] = fa[i-1][fa[i-1][x]];
	dfn[x] = ++dtot;
	for (auto e : con[x])
	{
		int u = e.FF;
		if (u==fa[0][x]) continue;
		fa[0][u] = x;
		len[u] = len[x]+e.SS;
		lv[u] = lv[x]+1;
		dfs(u);
	}
}
int get_lca(int x, int y)
{
	if (lv[x]>lv[y]) swap(x, y);
	for (int i=19; i>=0; i--) if (fa[i][y]&&lv[fa[i][y]]>=lv[x]) y = fa[i][y];
	if (x==y) return x;
	for (int i=19; i>=0; i--) if (fa[i][x]!=fa[i][y])
	{
		x = fa[i][x];
		y = fa[i][y];
	}
	return fa[0][x];	
}
void Init(int N, int A[], int B[], int D[])
{
	for (int i=0; i<maxn; i++) type[i] = 2;
	n = N;
	for (int i=0; i<n-1; i++)
	{
		int x = A[i], y = B[i], c = D[i];
		x++; y++;
		con[x].PB(MP(y, c));
		con[y].PB(MP(x, c));
	}
	len[1] = 0;
	lv[1] = 1;
	dfs(1);
}
bool cmp(int x, int y) {return dfn[x]<dfn[y];}
const ll inf = 4e18;
void upd(ll &x, ll v) {x=min(x, v);}
void add_edge(int x, int p) {ncon[p].PB(MP(x, len[x]-len[p]));}// cerr<<"add_edge:"<<p<<"->"<<x<<" "<<len[x]-len[p]<<endl;}
ll ans;
pair<ll,ll> calc_ans(int x)
{
	pair<ll,ll> ret = MP(inf, inf);
	if (type[x]==0) ret.FF = 0;
	if (type[x]==1) ret.SS = 0;
	for (auto e : ncon[x])
	{
		pair<ll,ll> pp = calc_ans(e.FF);
		upd(ret.FF, pp.FF+e.SS);
		upd(ret.SS, pp.SS+e.SS);
	}
	upd(ans, ret.FF+ret.SS);
	return ret;
}
long long Query(int S, int X[], int T, int Y[])
{
	vector<int> v;
	for (int i=0; i<S; i++) v.PB(X[i]+1), type[X[i]+1] = 0;
	for (int i=0; i<T; i++) v.PB(Y[i]+1), type[Y[i]+1] = 1;
	sort(v.begin(), v.end(), cmp);
	vector<int> st, all;
	st.PB(v[0]); all.PB(v[0]);
	for (int i=1; i<v.size(); i++)
	{
		int x = v[i];
		int p = get_lca(x, st.back());
//		cerr<<"x="<<x<<" last="<<st.back()<<" p="<<p<<endl;
		while (st.size()>=2&&len[st[st.size()-2]]>=len[p])
		{
			add_edge(st.back(), st[st.size()-2]);
			st.pop_back();
		}
		if (st.size()>0&&st.back()!=p) //add_edge p->left_most
		{
			add_edge(st.back(), p);
			st.pop_back();
		}
		if (st.size()==0||st.back()!=p) st.PB(p), all.PB(p);
		if (x!=p) st.PB(x), all.PB(x);
	}
	ans = inf;
	assert(st.size()>0);
	while (st.size()>1) add_edge(st.back(), st[st.size()-2]), st.pop_back();
	calc_ans(st[0]);
	for (auto t : all) ncon[t].clear(), type[t] = 2;
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:86:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<v.size(); i++)
                ~^~~~~~~~~

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