Task: | Tietoverkko |
Sender: | mbezirgan |
Submission time: | 2021-10-17 10:40:02 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 25 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | ACCEPTED | 15 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.32 s | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
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: TIME LIMIT EXCEEDED
input |
---|
200000 1 2 613084013 1 3 832364259 2 4 411999902 3 5 989696303 ... |
correct output |
---|
1080549209850010931 |
user output |
---|
(empty) |