CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:mbezirgan
Submission time:2021-10-17 10:40:02
Language:C++17
Status:READY
Result:25
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.32 s2, 3details
#3--3details

Code

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

struct Connection;

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

struct Connection
{
	Computer* a;
	Computer* b;
	uint64_t speed;
};

void FindAllPaths(uint64_t lowestSpeed, Computer* computer, Connection* connection, uint64_t* speed)
{
	for (auto& c : computer->connections)
	{
		if (c != connection)
		{

			uint64_t loopLowestSpeed = lowestSpeed;
			if (loopLowestSpeed > c->speed)
				loopLowestSpeed = c->speed;

			if (c->a != computer)
			{
				FindAllPaths(loopLowestSpeed, c->a, c, speed);
				*speed += loopLowestSpeed;
			}
			else
			{
				FindAllPaths(loopLowestSpeed, c->b, c, speed);
				*speed += loopLowestSpeed;
			}
		}
	}
}

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

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

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

	uint64_t speed = 0;

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

		c.a = a - 1 + computers;
		c.b = b - 1 + computers;

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

		std::cin >> c.speed;

		speed += c.speed;

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

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

		c.a = a - 1 + computers;
		c.b = b - 1 + computers;

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

		std::cin >> c.speed;

		Computer* computer = checked[c.a - computers] ? c.b : c.a;

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

		checked[computer - computers] = true;
	}

	std::cout << speed;

	delete[] connections;
	delete[] computers;
}

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: ACCEPTED

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

correct output
1103702320243776

user output
1103702320243776

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)