oj.uz

Submission #61194

# Submission time Handle Problem Language Result Execution time Memory
61194 2018-07-25T10:39:14 Z Eae02 Fireworks (APIO16_fireworks) C++14
0 / 100
 4 ms 632 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -