Submission #364834

#	Time	Username	Problem	Language	Result	Execution time	Memory
364834		Rainbowbunny	Factories (JOI14_factories)	C++17	100 / 100	3231 ms	221032 KiB

factories

#include "factories.h"

#include <iostream>
#include <algorithm>
#include <vector>

const long long INF = 1e17;

int timer;
int tin[500005], tout[500005], depth[500005];
int SparseTable[21][1000005], Log[1000005];
long long DistanceFromRoot[500005];
std::vector <std::pair <int, int> > Adj[500005];

void DFS(int node, int p = -1)
{
	SparseTable[0][timer] = node;
	tin[node] = timer;
	timer++;
	for(auto x : Adj[node])
	{
		if(x.first == p)
		{
			continue;
		}
		DistanceFromRoot[x.first] = DistanceFromRoot[node] + x.second;
		depth[x.first] = depth[node] + 1; 
		DFS(x.first, node);
		SparseTable[0][timer] = node;
		timer++;
	}
	tout[node] = timer;
}

int lower(int u, int v)
{
	return depth[u] < depth[v] ? u : v;
}

void BuildLCA()
{
	Log[0] = -1;
	for(int i = 1; i <= 1000000; i++)
	{
		Log[i] = Log[i >> 1] + 1;		
	}
	for(int i = 1; i <= 20; i++)
	{
		for(int j = 0; j + (1 << i) < 1000000; j++)
		{
			SparseTable[i][j] = lower(SparseTable[i - 1][j], SparseTable[i - 1][j + (1 << (i - 1))]);
		}
	}
}

int LCA(int u, int v)
{
	int l = std::min(tin[u], tin[v]), r = std::max(tin[u], tin[v]);
	return lower(SparseTable[Log[r - l + 1]][l], SparseTable[Log[r - l + 1]][r - (1 << Log[r - l + 1]) + 1]);
}

long long Distance(int u, int v)
{
	return DistanceFromRoot[u] + DistanceFromRoot[v] - 2 * DistanceFromRoot[LCA(u, v)];
}

void Init(int N, int A[], int B[], int D[])
{
	for(int i = 0; i < N - 1; i++)
	{
		Adj[A[i]].emplace_back(B[i], D[i]);
		Adj[B[i]].emplace_back(A[i], D[i]);
	}	
	DFS(0);
	BuildLCA();
}

int stack[500005], top;
int color[500005];
long long dp[500005][2];
std::vector <int> VirtualAdj[500005];

long long Solve(int node, int p = -1)
{
	long long ans = INF;
	dp[node][0] = dp[node][1] = INF;
	for(auto x : VirtualAdj[node])
	{
		if(x == p)
		{
			continue;
		}
		long long temp = Distance(x, node);
		ans = std::min(ans, Solve(x, node));
		if(dp[x][0] != INF)
		{
			dp[node][0] = std::min(dp[node][0], dp[x][0] + temp);
		}
		if(dp[x][1] != INF)
		{
			dp[node][1] = std::min(dp[node][1], dp[x][1] + temp);	
		} 
	}
	if(color[node] == 1)
	{
		dp[node][0] = 0;
	}
	if(color[node] == 2)
	{
		dp[node][1] = 0;
	}
	ans = std::min(ans, dp[node][0] + dp[node][1]);
	VirtualAdj[node].clear();
	color[node] = 0;
	return ans;
}

long long Query(int S, int X[], int T, int Y[])
{
	std::vector <int> Vertex;
	for(int i = 0; i < S; i++)
	{
		color[X[i]] = 1;
		Vertex.push_back(X[i]);
	}
	for(int i = 0; i < T; i++)
	{
		if(color[Y[i]] == 1)
		{
			for(auto x : Vertex)
			{
				color[x] = 0;
			}
			return 0;	
		}
		color[Y[i]] = 2;
		Vertex.push_back(Y[i]);
	}
	std::sort(Vertex.begin(), Vertex.end(), [](int u, int v){
		return tin[u] < tin[v];
	});
	top = 0;
	stack[0] = 0;
	for(auto x : Vertex)
	{
		if(x != 0)
		{
			int temp = LCA(x, stack[top]);
			if(temp != stack[top])
			{
				while(tin[temp] < tin[stack[top - 1]])
				{
					VirtualAdj[stack[top - 1]].push_back(stack[top]);
					VirtualAdj[stack[top]].push_back(stack[top - 1]);
					top--;
				}
				if(tin[temp] > tin[stack[top - 1]])
				{
					VirtualAdj[temp].push_back(stack[top]);
					VirtualAdj[stack[top]].push_back(temp);
					stack[top] = temp;
				}
				else
				{
					VirtualAdj[stack[top]].push_back(temp);
					VirtualAdj[temp].push_back(stack[top]);
					top--;
				}
			}
			top++;
			stack[top] = x;	
		}
	}
	for(int i = 0; i + 1 <= top; i++)
	{
		VirtualAdj[stack[i]].push_back(stack[i + 1]);
		VirtualAdj[stack[i + 1]].push_back(stack[i]);
	}
	return Solve(0);	
}

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