Tietoverkko

#include <iostream>
#include <string>
#include <vector>
#include <memory>

inline uint32_t SumFactorial(uint32_t n)
{
	uint32_t a = 0;

	for (uint32_t i = 1; i < n; i++)
		a += i;

	return a;
}

static uint32_t* stash;

inline uint32_t SumFactorialRev(uint32_t n, uint32_t a)
{
	if (stash[a])
		return stash[a];

	uint32_t b = 0;

	for (uint32_t i = 0; i < a; i++)
		b += n - 1 - i;

	stash[a] = b;
	return b;
}

int main()
{
	uint32_t n;
	std::cin >> n;

	// Access has to be done using size n and computer id a, b where a is smaller then b as
	// [b - a - 1 + SumFactorialRev(n, a)]
	uint32_t* connections = new uint32_t[SumFactorial(n)];
	stash = new	uint32_t[n]();
	bool* checked = new bool[n]();

	uint64_t totalSpeed = 0;

	// For this to work the fastest way possible the input should be put in order

	// First input
	{
		uint32_t a, b;
		std::cin >> a;
		std::cin >> b;
		a -= 1;
		b -= 1;

		uint32_t speed;
		std::cin >> speed;

		totalSpeed += speed;

		uint32_t c1 = a > b ? b : a;
		uint32_t c2 = a > b ? a : b;

		connections[c2 - c1 - 1 + SumFactorialRev(n, c1)] = speed;

		checked[a] = true;
		checked[b] = true;
	}

	for (uint32_t i = 1; i < n - 1; i++)
	{
		uint32_t a, b;
		std::cin >> a;
		std::cin >> b;
		a -= 1;
		b -= 1;

		uint32_t speed;
		std::cin >> speed;

		totalSpeed += speed;

		uint32_t c1 = a > b ? b : a;
		uint32_t c2 = a > b ? a : b;

		connections[c2 - c1 - 1 + SumFactorialRev(n, c1)] = speed;

		uint32_t cA = checked[a] ? a : b;
		uint32_t cB = checked[a] ? b : a;

		// Loop through all known computers
		for (uint32_t j = 0; j < i + 1; j++)
		{
			if (j == cA)
				continue;

			c1 = j > cA ? cA : j;
			c2 = j > cA ? j : cA;

			uint32_t lowestSpeed = connections[c2 - c1 - 1 + SumFactorialRev(n, c1)];
			lowestSpeed = lowestSpeed > speed ? speed : lowestSpeed;

			c1 = j > cB ? cB : j;
			c2 = j > cB ? j : cB;

			connections[c2 - c1 - 1 + SumFactorialRev(n, c1)] = lowestSpeed;

			totalSpeed += lowestSpeed;
		}

		checked[cB] = true;
	}

	std::cout << totalSpeed;

	delete[] connections;
	delete[] checked;
	delete[] stash;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc