Submission #126589

#	Time	Username	Problem	Language	Result	Execution time	Memory
126589		fjzzq2002	Factories (JOI14_factories)	C++14	18 / 100	8016 ms	94368 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ 2234567
typedef long long ll;
int n,M=0,fst[SZ],vb[SZ],nxt[SZ]; ll vc[SZ];
void ad_de(int a,int b,ll c)
{
	++M; nxt[M]=fst[a]; fst[a]=M;
	vb[M]=b; vc[M]=c;
}
void adde(int a,int b,ll c)
{
	ad_de(a,b,c); ad_de(b,a,c);
}
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
int dep[SZ],sz[SZ],so[SZ],fa[SZ]; ll dd[SZ];
void dfs1(int x,int fa=0)
{
	sz[x]=1; dep[x]=dep[fa]+1; ::fa[x]=fa;
	for esb(x,e,b) if(b!=fa)
	{
		dd[b]=dd[x]+vc[e];
		dfs1(b,x),sz[x]+=sz[b];
		if(sz[b]>sz[so[x]]) so[x]=b;
	}
}
int top[SZ],dn[SZ],D,rv[SZ];
void dfs2(int x,int t,int fa=0)
{
	top[x]=t; dn[x]=++D; rv[D]=x;
	if(so[x]) dfs2(so[x],t,x);
	for esb(x,e,b) if(b!=fa&&b!=so[x])
		dfs2(b,b,x);
}
int lca(int a,int b)
{
	while(top[a]!=top[b])
	{
		if(dep[top[a]]>dep[top[b]]) swap(a,b);
		b=fa[top[b]];
	}
	if(dep[a]<dep[b]) return a;
	return b;
}
ll dis(int a,int b)
{
	return dd[a]+dd[b]-dd[lca(a,b)]*2;
}
void Init(int N, int A[], int B[], int D[]) {
	n=N;
	for(int i=0;i<n-1;++i)
		adde(A[i]+1,B[i]+1,D[i]);
	dfs1(1); dfs2(1,1);
}
typedef pair<int,int> pii;
pii p[SZ]; int pn;
#define fi first
#define se second
int st[SZ],sn,vs[SZ],vn,vfa[SZ],typ[SZ];
ll fd[SZ],fu[SZ];
void d1(int x)
{
	fd[x]=4e18;
	if(typ[x]==1) fd[x]=0;
	for esb(x,e,b)
		d1(b),fd[x]=min(fd[x],fd[b]+vc[e]);
}
#define pb push_back
#define mp make_pair
void d2(int x)
{
	if(typ[x]==1) fu[x]=0;
	{
	vector<pair<ll,int>> tmp;
	tmp.pb(mp(fu[x],0));
	for esb(x,e,b)
		tmp.pb(mp(fd[b]+vc[e],b));
	sort(tmp.begin(),tmp.end());
	for esb(x,e,b)
		for(int j=0;j<2&&j<tmp.size();++j)
			if(tmp[j].se!=b)
				fu[b]=min(fu[b],tmp[j].fi+vc[e]);
	}
	for esb(x,e,b) d2(b);
}
ll gans(int r)
{
	d1(r);
	for(int i=1;i<=vn;++i) fu[vs[i]]=4e18;
	d2(r);
//	for(int i=1;i<=vn;++i)
//		cout<<vs[i]<<":"<<fu[vs[i]]<<"w"<<fd[vs[i]]<<" "<<vfa[vs[i]]<<" "<<typ[vs[i]]<<"?\n";
	ll ans=4e18;
	for(int i=1;i<=vn;++i)
		if(typ[vs[i]]==2)
			ans=min(ans,min(fu[vs[i]],fd[vs[i]]));
	return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
	ll ans=8e18;
	for(int i=0;i<S;++i)
		for(int j=0;j<T;++j)
			ans=min(ans,dis(X[i]+1,Y[j]+1));
	return ans;
	pn=sn=vn=0;
	for(int i=0;i<S;++i)
		p[++pn]=pii(dn[X[i]+1],1);
	for(int i=0;i<T;++i)
		p[++pn]=pii(dn[Y[i]+1],2);
	sort(p+1,p+1+pn);
	for(int i=1;i<=pn;++i)
	{
		int x=rv[p[i].fi]; vs[++vn]=x;
		if(!sn)
		{
			st[++sn]=x;
			vfa[x]=0;
			continue;
		}
		int g=lca(st[sn],x);
		while(sn&&dep[st[sn]]>dep[g])
			vfa[st[sn]]=g,--sn;
		if(st[sn]!=g)
			st[++sn]=g,
			vfa[g]=st[sn-1],
			vs[++vn]=g;
		vfa[x]=st[sn];
		st[++sn]=x;
	}
	M=0;
	for(int i=1;i<=vn;++i)
		fst[vs[i]]=typ[vs[i]]=0;
	for(int i=1;i<=pn;++i)
		typ[rv[p[i].fi]]=p[i].se;
	int root=-1;
	for(int i=1;i<=vn;++i)
		if(vfa[vs[i]])
//			cout<<vfa[vs[i]]<<"->"<<vs[i]<<"\n",
			ad_de(vfa[vs[i]],vs[i],dd[vs[i]]-dd[vfa[vs[i]]]);
		else root=vs[i];
//	cout<<root<<"!\n";
	return gans(root);
}
#ifdef LOCAL
#define D D__
#include "grader.cpp"
#endif

Compilation message (stderr)

factories.cpp: In function 'void d2(int)':
factories.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<2&&j<tmp.size();++j)
                    ~^~~~~~~~~~~

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