Submission #222935

#	Time	Username	Problem	Language	Result	Execution time	Memory
222935		arnold518	Factories (JOI14_factories)	C++14	0 / 100	21 ms	12544 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;
const ll INF = 1e18;

int N;
vector<pii> adj[MAXN+10];

int sz[MAXN+10], del[MAXN+10], cenpar[MAXN+10], cendep[MAXN+10];
ll dist[MAXN+10][30];

void getsz(int now, int bef)
{
	sz[now]=1;
	for(auto &nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		getsz(nxt.first, now);
		sz[now]+=sz[nxt.first];
	}
}

int getcen(int now, int bef, int S)
{
	for(auto &nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		if(sz[nxt.first]>S/2) return getcen(nxt.first, now, S);
	}
	return now;
}

void dfs(int now, int bef, ll d, int cdep)
{
	dist[now][cdep]=d;
	for(auto &nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		dfs(nxt.first, now, d+nxt.second, cdep);
	}
}

void decomp(int now, int cdep)
{
	getsz(now, now);
	now=getcen(now, now, sz[now]);
	cendep[now]=cdep;
		
	dfs(now, now, 0, cdep);

	del[now]=true;
	for(auto &nxt : adj[now])
	{
		if(del[nxt.first]) continue;
		cenpar[nxt.first]=now;
		decomp(nxt.first, cdep+1);
	}
}

ll A[MAXN+10], B[MAXN+10];

void Init(int _N, int AA[], int BB[], int D[])
{
	int i, j;
	N=_N;
	for(i=0; i<N-1; i++)
	{
		int u=AA[i]+1, v=BB[i]+1, w=D[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	decomp(1, 1);
	for(i=1; i<=N; i++) A[i]=B[i]=INF;
}

ll Query(int S, int X[], int T, int Y[])
{
	int i, j;

	vector<int> V;
	for(i=0; i<S; i++)
	{
		int now=X[i]+1, u=X[i]+1;
		while(now)
		{
			A[now]=min(A[now], dist[u][cendep[now]]);
			V.push_back(now);
			now=cenpar[now];
		}
	}

	for(i=0; i<T; i++)
	{
		int now=Y[i]+1, u=Y[i]+1;
		while(now)
		{
			B[now]=min(B[now], dist[u][cendep[now]]);
			V.push_back(now);
			now=cenpar[now];
		}
	}

	ll ans=INF;
	for(auto it : V) ans=min(ans, A[it]+B[it]);
	for(auto it : V) A[it]=B[it]=INF;
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:73:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:87:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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