Submission #126613

#	Time	Username	Problem	Language	Result	Execution time	Memory
126613		fizzydavid	Factories (JOI14_factories)	C++14	100 / 100	2825 ms	113784 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 lv[maxn], fa[maxn], top[maxn], arr[maxn], sz[maxn], son[maxn];
ll len[maxn];
int dfn[maxn], dtot;
vector<pair<int,ll> > ncon[maxn];
int type[maxn];

void dfs(int x)
{
	sz[x] = 1;
	for (auto e : con[x])
	{
		int u = e.FF;
		if (u==fa[x]) continue;
		fa[u] = x;
		len[u] = len[x]+e.SS;
		lv[u] = lv[x]+1;
		dfs(u);
		sz[x] += sz[u];
		if (!son[x]||sz[u]>sz[son[x]]) son[x] = u;
	}
}
void dfs2(int x, int tp)
{
	dfn[x] = ++dtot; arr[dtot] = x;
	top[x] = tp;
	if (son[x]) dfs2(son[x], tp);
	for (auto e : con[x])
	{
		int u = e.FF;
		if (u==fa[x]||u==son[x]) continue;
		dfs2(u, u);
	}
}
int get_lca(int x, int y)
{
	while (true)
	{
		if (top[x]==top[y]) return arr[min(dfn[x], dfn[y])];
		else
		{
			if (lv[top[x]]>lv[top[y]]) x = fa[top[x]];
			else y = fa[top[y]];
		}
	}
}
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);
	dfs2(1, 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:101: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: 67 / 67