oj.uz

Submission #364834

# Submission time Handle Problem Language Result Execution time Memory
364834 2021-02-10T08:12:45 Z Rainbowbunny Factories (JOI14_factories) C++17
100 / 100
 3231 ms 221032 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 98688 KB Output is correct
2 Correct 695 ms 116236 KB Output is correct
3 Correct 772 ms 116300 KB Output is correct
4 Correct 700 ms 116376 KB Output is correct
5 Correct 625 ms 116672 KB Output is correct
6 Correct 605 ms 116432 KB Output is correct
7 Correct 744 ms 116320 KB Output is correct
8 Correct 693 ms 116332 KB Output is correct
9 Correct 620 ms 116716 KB Output is correct
10 Correct 599 ms 116204 KB Output is correct
11 Correct 765 ms 116460 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 98284 KB Output is correct
2 Correct 1757 ms 171264 KB Output is correct
3 Correct 1973 ms 182308 KB Output is correct
4 Correct 1430 ms 171092 KB Output is correct
5 Correct 1580 ms 201196 KB Output is correct
6 Correct 2088 ms 174060 KB Output is correct
7 Correct 1863 ms 131144 KB Output is correct
8 Correct 1236 ms 132448 KB Output is correct
9 Correct 1169 ms 136556 KB Output is correct
10 Correct 1843 ms 133784 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 98688 KB Output is correct
2 Correct 695 ms 116236 KB Output is correct
3 Correct 772 ms 116300 KB Output is correct
4 Correct 700 ms 116376 KB Output is correct
5 Correct 625 ms 116672 KB Output is correct
6 Correct 605 ms 116432 KB Output is correct
7 Correct 744 ms 116320 KB Output is correct
8 Correct 693 ms 116332 KB Output is correct
9 Correct 620 ms 116716 KB Output is correct
10 Correct 599 ms 116204 KB Output is correct
11 Correct 765 ms 116460 KB Output is correct
12 Correct 88 ms 98284 KB Output is correct
13 Correct 1757 ms 171264 KB Output is correct
14 Correct 1973 ms 182308 KB Output is correct
15 Correct 1430 ms 171092 KB Output is correct
16 Correct 1580 ms 201196 KB Output is correct
17 Correct 2088 ms 174060 KB Output is correct
18 Correct 1863 ms 131144 KB Output is correct
19 Correct 1236 ms 132448 KB Output is correct
20 Correct 1169 ms 136556 KB Output is correct
21 Correct 1843 ms 133784 KB Output is correct
22 Correct 2797 ms 194952 KB Output is correct
23 Correct 2725 ms 197240 KB Output is correct
24 Correct 3111 ms 197552 KB Output is correct
25 Correct 3036 ms 200748 KB Output is correct
26 Correct 3189 ms 197104 KB Output is correct
27 Correct 2476 ms 221032 KB Output is correct
28 Correct 1977 ms 198484 KB Output is correct
29 Correct 3231 ms 196332 KB Output is correct
30 Correct 3134 ms 195828 KB Output is correct
31 Correct 3173 ms 196512 KB Output is correct
32 Correct 1217 ms 140768 KB Output is correct
33 Correct 1072 ms 137056 KB Output is correct
34 Correct 1529 ms 132528 KB Output is correct
35 Correct 1538 ms 132588 KB Output is correct
36 Correct 1723 ms 133256 KB Output is correct
37 Correct 1811 ms 132864 KB Output is correct