Submission #62129

#	Time	Username	Problem	Language	Result	Execution time	Memory
62129		mohammedehab2002	Factories (JOI14_factories)	C++11	0 / 100	4989 ms	425072 KiB

factories

#include "factories.h"
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int,int> > v[500005];
long long cum[500005],di[30][500005];
bool del[500005];
int dep[500005],dp[20][500005],par[500005],sz[500005];
void dfs(int node,int p)
{
	for (auto u:v[node])
	{
		if (u.first!=p)
		{
			dep[u.first]=dep[node]+1;
			cum[u.first]=cum[node]+u.second;
			dp[0][u.first]=node;
			dfs(u.first,node);
		}
	}
}
int lca(int u,int v)
{
	if (dep[u]<dep[v])
	swap(u,v);
	int d=dep[u]-dep[v];
	for (int i=0;i<20;i++)
	{
		if (d&(1<<i))
		u=dp[i][u];
	}
	if (u==v)
	return u;
	for (int i=19;i>=0;i--)
	{
		if (dp[i][u]!=dp[i][v])
		{
			u=dp[i][u];
			v=dp[i][v];
		}
	}
	return dp[0][u];
}
long long dist(int a,int b)
{
	return cum[a]+cum[b]-2*cum[lca(a,b)];
}
void pre(int node,int p)
{
	sz[node]=1;
	for (auto u:v[node])
	{
		if (!del[u.first] && u.first!=p)
		{
			dfs(u.first,node);
			sz[node]+=sz[u.first];
		}
	}
}
int find(int node,int p,int n)
{
	for (auto u:v[node])
	{
		if (u.first!=p && !del[u.first] && sz[u.first]>n/2)
		return find(u.first,node,n);
	}
	return node;
}
void dfs2(int node,int p)
{
	pre(node,-1);
	int c=find(node,-1,sz[node]);
	par[c]=p;
	del[c]=1;
	for (auto u:v[c])
	{
		if (!del[u.first])
		dfs2(u.first,c);
	}
}
long long ans[500005];
void update(int node,bool mem)
{
	int cur=node,cnt=0;
	while (cur!=-1)
	{
		if (di[cnt][node]==-1)
		di[cnt][node]=dist(cur,node);
		if (mem)
		ans[cur]=(1LL<<60);
		else
		ans[cur]=min(ans[cur],di[cnt][node]);
		cur=par[cur];
		cnt++;
	}
}
long long query(int node)
{
	int cur=node,cnt=0;
	long long ret=(1LL<<60);
	while (cur!=-1)
	{
		ret=min(ret,di[cnt][node]+ans[cur]);
		cur=par[cur];
		cnt++;
	}
	return ret;
}
void Init(int n,int a[],int b[],int d[])
{
	for (int i=0;i<n-1;i++)
	{
		v[a[i]].push_back({b[i],d[i]});
		v[b[i]].push_back({a[i],d[i]});
	}
	memset(dp,-1,sizeof(dp));
	dfs(0,-1);
	for (int i=1;i<20;i++)
	{
		for (int x=0;x<n;x++)
		{
			if (dp[i-1][x]!=-1)
			dp[i][x]=dp[i-1][dp[i-1][x]];
		}
	}
	memset(di,-1,sizeof(di));
	dfs2(0,-1);
	for (int i=0;i<n;i++)
	update(i,1);
}
long long Query(int s,int x[],int t,int y[])
{
	/*long long ret=(1LL<<60);
	for (int i=0;i<s;i++)
	{
		for (int j=0;j<t;j++)
		ret=min(ret,dist(x[i],y[j]));
	}
	return ret;*/
	for (int i=0;i<s;i++)
	update(x[i],0);
	long long ret=(1LL<<60);
	for (int i=0;i<t;i++)
	ret=min(ret,query(y[i]));
	for (int i=0;i<s;i++)
	update(x[i],1);
	return ret;
}

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