Submission #61194

#	Time	Username	Problem	Language	Result	Execution time	Memory
61194		Eae02	Fireworks (APIO16_fireworks)	C++14	0 / 100	4 ms	632 KiB

fireworks

#include <bits/stdc++.h>

struct Fuse
{
	struct Node* other = nullptr;
	int len;
};

struct Node
{
	int dist = 0;
	Fuse toParent;
	int fuseDelta;
	bool isExplosive;
	std::vector<Fuse> children;
	std::vector<Fuse> connected;
};

void initDelta(Node* node)
{
	for (const Fuse& f : node->children)
	{
		if (!f.other->isExplosive)
			initDelta(f.other);
	}
	
	while (true)
	{
		int costP = 1;
		int costN = 1;
		
		for (const Fuse& f : node->children)
		{
			costP += f.other->fuseDelta > 0 ? -1 : 1;
			costN += f.other->fuseDelta < 0 ? -1 : 1;
		}
		
		int d;
		if (costP < 0)
			d = 1;
		else if (costN < 0)
			d = -1;
		else
			break;
		
		node->fuseDelta += d;
		for (const Fuse& f : node->children)
			f.other->fuseDelta -= d;
	}
}

void genTree(Node* node)
{
	for (const Fuse& child : node->connected)
	{
		if (!child.other->children.empty())
			continue;
		
		child.other->dist = node->dist + child.len;
		node->children.push_back(child);
		child.other->toParent = { node, child.len };
		
		genTree(child.other);
	}
}

int main()
{
	int numJ, numE;
	std::cin >> numJ;
	std::cin >> numE;
	
	std::vector<Node> nodes(numJ + numE);
	Node* sw = nullptr;
	
	for (int i = 0; i < numJ + numE; i++)
		nodes[i].isExplosive = i >= numJ;
	
	for (int i = 0; i < numJ + numE - 1; i++)
	{
		int n, len;
		std::cin >> n;
		std::cin >> len;
		n--;
		
		nodes[i + 1].connected.push_back(Fuse { &nodes[n], len });
		nodes[n].connected.push_back(Fuse { &nodes[i + 1], len });
	}
	
	for (int i = 0; i < numJ; i++)
	{
		if (nodes[i].connected.size() == 1)
		{
			sw = &nodes[i];
			break;
		}
	}
	
	genTree(sw);
	
	int minDist = INT32_MAX;
	int maxDist = INT32_MIN;
	for (int i = 0; i < numE; i++)
	{
		minDist = std::min(nodes[numJ + i].dist, minDist);
		maxDist = std::max(nodes[numJ + i].dist, maxDist);
	}
	
	int minCost = INT32_MAX;
	
	for (int target = minDist; target <= maxDist; target++)
	{
		for (int i = 0; i < numJ; i++)
		{
			nodes[i].fuseDelta = 0;
		}
		for (int i = 0; i < numE; i++)
		{
			nodes[numJ + i].fuseDelta = target - nodes[numJ + i].dist;
		}
		
		initDelta(sw->children[0].other);
		
		int cost = 0;
		for (int i = 0; i < numJ + numE; i++)
		{
			cost += std::abs(nodes[i].fuseDelta);
		}
		minCost = std::min(cost, minCost);
	}
	
	std::cout << minCost << std::endl;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45