CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:mbezirgan
Submission time:2021-10-17 12:31:43
Language:C++17
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2--2, 3details
#30.01 s3details

Code

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

inline uint32_t SumFactorialRev(uint32_t n, uint32_t a)
{
	uint32_t b = 0;

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

	return b;
}

int main()
{
	uint64_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)];
	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;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
(empty)

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)

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