Tietoverkko

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

// In my opinion this should be the answer as this is BY far the fastest possible but oh well
#if 0

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;
}

#else

struct Connection;

struct Computer
{
	std::vector<Connection*> connections;
};

struct Connection
{
	Computer* other;
	uint64_t speed;
};

uint32_t FindConnectionSize(Computer* computer, Computer* sender)
{
	uint32_t size = 1;

	for (auto& c : computer->connections)
	{
		if (c->other != sender)
		{
			size += FindConnectionSize(c->other, computer);
		}
	}

	return size;
}

void FindAllPaths(uint64_t lowestSpeed, Computer* computer, Computer* sender, uint64_t* speed)
{
	for (auto& c : computer->connections)
	{
		if (c->other != sender)
		{
			uint64_t loopLowestSpeed = lowestSpeed;
			if (loopLowestSpeed > c->speed)
				loopLowestSpeed = c->speed;

			if (loopLowestSpeed == 1)
			{
				if (c->other->connections.size() == 1)
					*speed += 1;
				else
					*speed += FindConnectionSize(c->other, computer);
			}
			else
			{
				FindAllPaths(loopLowestSpeed, c->other, computer, speed);
				*speed += loopLowestSpeed;
			}
		}
	}
}

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

	Computer* computers = new Computer[n]();
	Connection* connections = new Connection[2*(n - 1)];

	bool* checked = new bool[n]();

	uint64_t speed = 0;

	// First input
	{
		auto& c1 = connections[0];
		auto& c2 = connections[1];
		uint64_t a, b;
		std::cin >> a;
		std::cin >> b;

		std::cin >> c1.speed;
		c2.speed = c1.speed;

		c1.other = a - 1 + computers;
		c2.other = b - 1 + computers;

		computers[a - 1].connections.push_back(&c2);
		computers[b - 1].connections.push_back(&c1);

		speed += c1.speed;

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

	for (uint64_t i = 1; i < n - 1; i++)
	{
		auto& c1 = connections[2*i];
		auto& c2 = connections[2*i + 1];
		uint64_t a, b;
		std::cin >> a;
		std::cin >> b;

		std::cin >> c1.speed;
		c2.speed = c1.speed;

		c1.other = a - 1 + computers;
		c2.other = b - 1 + computers;

		computers[a - 1].connections.push_back(&c2);
		computers[b - 1].connections.push_back(&c1);

		Computer* computer = checked[a - 1] ? c2.other : c1.other;

		if (c1.speed == 1)
		{
			speed += i + 1;
		}
		else
		{
			FindAllPaths(UINT32_MAX, computer, nullptr, &speed);
		}

		checked[computer - computers] = true;
	}

	std::cout << speed;

	delete[] connections;
	delete[] computers;
}

#endif

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED