oj.uz

Submission #126593

# Submission time Handle Problem Language Result Execution time Memory
126593 2019-07-08T07:16:23 Z fjzzq2002 Factories (JOI14_factories) C++14
100 / 100
 2990 ms 111344 KB 
#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[]) {
	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;
//		cout<<x<<"!!\n";
		if(!sn)
		{
			st[++sn]=x;
			vfa[x]=0;
			continue;
		}
		int g=lca(st[sn],x);
//		cout<<g<<"?\n";
		while(sn&&dep[st[sn]]>dep[g])
		{
			if(dep[st[sn-1]]<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

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1016 KB Output is correct
2 Correct 892 ms 12940 KB Output is correct
3 Correct 972 ms 18652 KB Output is correct
4 Correct 878 ms 18652 KB Output is correct
5 Correct 717 ms 18808 KB Output is correct
6 Correct 762 ms 18744 KB Output is correct
7 Correct 970 ms 18632 KB Output is correct
8 Correct 876 ms 18724 KB Output is correct
9 Correct 718 ms 18936 KB Output is correct
10 Correct 784 ms 18696 KB Output is correct
11 Correct 999 ms 18680 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 1729 ms 63404 KB Output is correct
3 Correct 1540 ms 65292 KB Output is correct
4 Correct 1134 ms 61048 KB Output is correct
5 Correct 1294 ms 90360 KB Output is correct
6 Correct 1645 ms 66652 KB Output is correct
7 Correct 1532 ms 24904 KB Output is correct
8 Correct 936 ms 25048 KB Output is correct
9 Correct 1065 ms 29048 KB Output is correct
10 Correct 1424 ms 36364 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1016 KB Output is correct
2 Correct 892 ms 12940 KB Output is correct
3 Correct 972 ms 18652 KB Output is correct
4 Correct 878 ms 18652 KB Output is correct
5 Correct 717 ms 18808 KB Output is correct
6 Correct 762 ms 18744 KB Output is correct
7 Correct 970 ms 18632 KB Output is correct
8 Correct 876 ms 18724 KB Output is correct
9 Correct 718 ms 18936 KB Output is correct
10 Correct 784 ms 18696 KB Output is correct
11 Correct 999 ms 18680 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 1729 ms 63404 KB Output is correct
14 Correct 1540 ms 65292 KB Output is correct
15 Correct 1134 ms 61048 KB Output is correct
16 Correct 1294 ms 90360 KB Output is correct
17 Correct 1645 ms 66652 KB Output is correct
18 Correct 1532 ms 24904 KB Output is correct
19 Correct 936 ms 25048 KB Output is correct
20 Correct 1065 ms 29048 KB Output is correct
21 Correct 1424 ms 36364 KB Output is correct
22 Correct 2763 ms 87224 KB Output is correct
23 Correct 2684 ms 90116 KB Output is correct
24 Correct 2737 ms 89788 KB Output is correct
25 Correct 2705 ms 93560 KB Output is correct
26 Correct 2876 ms 88576 KB Output is correct
27 Correct 2453 ms 111344 KB Output is correct
28 Correct 2057 ms 90004 KB Output is correct
29 Correct 2990 ms 87932 KB Output is correct
30 Correct 2896 ms 87832 KB Output is correct
31 Correct 2905 ms 88380 KB Output is correct
32 Correct 1278 ms 41964 KB Output is correct
33 Correct 1266 ms 38224 KB Output is correct
34 Correct 1610 ms 32632 KB Output is correct
35 Correct 1569 ms 32536 KB Output is correct
36 Correct 1588 ms 33248 KB Output is correct
37 Correct 1620 ms 33204 KB Output is correct