CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:chaotic
Submission time:2022-11-02 22:06:00 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.00 s1, 2details
#20.00 s1, 2details
#30.00 s1, 2details
#40.00 s1, 2details
#50.00 s1, 2details
#60.00 s1, 2details
#70.03 s2details
#80.00 s1, 2details
#90.03 s2details
#100.00 s1, 2details
#110.03 s2details
#120.11 s2details
#130.11 s2details
#140.10 s2details
#150.00 s1, 2details
#160.00 s1, 2details
#170.00 s1, 2details
#180.00 s1, 2details
#190.00 s1, 2details
#200.00 s1, 2details
#210.10 s2details
#220.11 s2details
#230.10 s2details
#240.00 s1, 2details
#250.10 s2details
#260.00 s1, 2details
#270.10 s2details
#280.01 s1, 2details
#290.10 s2details
#300.00 s1, 2details
#310.10 s2details

Code

#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <memory>
#include <numeric>
#include <sstream>
#include <vector>
using ll = long long;
struct City {
City* left = nullptr;
City* right = nullptr;
ll left_dist;
ll right_dist;
bool port;
ll shortest_down = LLONG_MAX;
bool has_parent = false;
void connect(City& o, ll dist) {
assert(o.has_parent == false);
if (!left) {
left = &o;
left_dist = dist;
} else {
assert(!right);
right = &o;
right_dist = dist;
}
o.has_parent = true;
}
void calc_down() {
if (port) {
shortest_down = 0;
return;
}
ll l = LLONG_MAX;
ll r = LLONG_MAX;
if (left) {
left->calc_down();
l = left->shortest_down;
}
if (right) {
right->calc_down();
r = right->shortest_down;
}
auto add = [](ll a, ll b) {
if (a == LLONG_MAX || b == LLONG_MAX) return LLONG_MAX;
return a + b;
};
shortest_down = std::min(add(l, left_dist), add(r, right_dist));
}
ll shortest = LLONG_MAX;
void calc_shortest(ll up_dist, City* p) {
if (!p) {
shortest = shortest_down;
} else if (port) {
shortest = 0;
} else {
auto add = [](ll a, ll b) {
if (a == LLONG_MAX || b == LLONG_MAX) return LLONG_MAX;
return a + b;
};
ll l = left ? add(left->shortest_down, left_dist) : LLONG_MAX;
ll r = right ? add(right->shortest_down, right_dist) : LLONG_MAX;
shortest = std::min(std::min(l, r), add(p->shortest, up_dist));
}
if (left) left->calc_shortest(left_dist, this);
if (right) right->calc_shortest(right_dist, this);
}
};
int main() {
std::cin.sync_with_stdio(false);
auto& stream = std::cin;
// std::stringstream ss{ R"(6
// 1 1 0 0 1 1
// 1 2 20
// 2 3 30
// 2 5 50
// 3 6 60
// 1 4 10)" };
// ss.copyfmt(std::cin);
// ss.exceptions(ss.badbit | ss.failbit);
// auto& stream = ss;
int n;
stream >> n;
std::vector<City> cities;
cities.reserve(n);
for (int i = 0; i < n; ++i) {
//
int v;
stream >> v;
City nw;
nw.port = v == 0 ? true : false;
cities.push_back(nw);
}
for (int i = 0; i < n - 1; ++i) {
int a, b, c;
stream >> a >> b >> c;
cities[a - 1].connect(cities[b - 1], c);
}
City* root;
for (auto& c : cities) {
if (c.has_parent == false) {
root = &c;
break;
}
}
std::cout << root << "\n";
root->calc_down();
root->calc_shortest(LLONG_MAX, nullptr);
std::cout << root->shortest_down << "\n";
ll sum = 0;
for (auto& c : cities) {
std::cout << c.shortest << "\n";
sum += c.shortest;
}
std::cout << "\n" << sum << "\n";
}

Test details

Test 1

Group: 1, 2

Verdict:

input
1
0

correct output
0

user output
0x555555589f10
0
0

0

Test 2

Group: 1, 2

Verdict:

input
5
0 0 0 0 0
1 2 1
2 3 2
3 4 3
...

correct output
0

user output
0x555555589f10
0
0
0
0
...

Test 3

Group: 1, 2

Verdict:

input
4
1 0 1 1
1 2 10
2 3 20
2 4 30

correct output
60

user output
0x555555589f10
10
10
0
20
...

Test 4

Group: 1, 2

Verdict:

input
5
0 1 1 1 0
1 2 10
2 3 20
3 4 30
...

correct output
80

user output
0x555555589f10
0
0
10
30
...

Test 5

Group: 1, 2

Verdict:

input
5
0 1 0 1 1
1 2 1
2 3 5
3 4 3
...

correct output
6

user output
0x555555589f10
0
0
1
0
...

Test 6

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5506363

user output
(empty)

Error:
code: input/code.cpp:24: void City::connect(City&, ll): Assertion `o.has_parent == false'...

Test 7

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1795118520

user output
(empty)

Error:
code: input/code.cpp:24: void City::connect(City&, ll): Assertion `o.has_parent == false'...

Test 8

Group: 1, 2

Verdict:

input
1000
0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 ...

correct output
293576

user output
(empty)

Error:
code: input/code.cpp:24: void City::connect(City&, ll): Assertion `o.has_parent == false'...

Test 9

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
816932444

user output
(empty)

Error:
code: input/code.cpp:24: void City::connect(City&, ll): Assertion `o.has_parent == false'...

Test 10

Group: 1, 2

Verdict:

input
1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
3089

user output
(empty)

Error:
code: input/code.cpp:24: void City::connect(City&, ll): Assertion `o.has_parent == false'...

Test 11

Group: 2

Verdict:

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
40839

user output
(empty)

Error:
code: input/code.cpp:24: void City::connect(City&, ll): Assertion `o.has_parent == false'...

Test 12

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5683983203973

user output
0x15555437f010
31678615
31678615
31678307
31677627
...
Truncated

Test 13

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 ...

correct output
58572993

user output
0x15555437f010
0
0
46
379
...
Truncated

Test 14

Group: 2

Verdict:

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
32755

user output
0x15555437f010
0
0
0
0
...
Truncated

Test 15

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
126238345

user output
0x555555589f10
237418
237418
237022
236479
...
Truncated

Test 16

Group: 1, 2

Verdict:

input
1000
0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 ...

correct output
278678

user output
0x555555589f10
0
0
0
0
...
Truncated

Test 17

Group: 1, 2

Verdict:

input
1000
1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 ...

correct output
34929

user output
0x555555589f10
444
444
0
0
...
Truncated

Test 18

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1543963

user output
0x555555589f10
1810
1810
986
1652
...
Truncated

Test 19

Group: 1, 2

Verdict:

input
1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
39606

user output
0x555555589f10
0
0
0
0
...
Truncated

Test 20

Group: 1, 2

Verdict:

input
1000
1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 ...

correct output
321598

user output
0x555555589f10
60
60
0
41
...
Truncated

Test 21

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
978670626

user output
0x15555437f010
3535
3535
3799
3284
...
Truncated

Test 22

Group: 2

Verdict:

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
375218

user output
0x15555437f010
0
0
0
0
...
Truncated

Test 23

Group: 2

Verdict:

input
200000
1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 ...

correct output
60422556

user output
0x15555437f010
927
927
144
657
...
Truncated

Test 24

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
291990

user output
0x555555589f10
3058
3058
2412
2442
...
Truncated

Test 25

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
59607954

user output
0x15555437f010
4883
4883
4098
4178
...
Truncated

Test 26

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
990

user output
0x555555589f10
8
8
8
7
...
Truncated

Test 27

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
199982

user output
0x15555437f010
16
16
16
15
...
Truncated

Test 28

Group: 1, 2

Verdict:

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
7987

user output
0x555555589f10
0
0
1
1
...
Truncated

Test 29

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
3137875

user output
0x15555437f010
0
0
1
1
...
Truncated

Test 30

Group: 1, 2

Verdict:

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
4657693

user output
0x555555589f10
0
0
583
950
...
Truncated

Test 31

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1652889357

user output
0x15555437f010
0
0
857
730
...
Truncated