CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:chaotic
Submission time:2022-11-02 22:12:01 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#2ACCEPTED0.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#40.00 s1, 2details
#5ACCEPTED0.00 s1, 2details
#6--1, 2details
#7--2details
#8--1, 2details
#9--2details
#10--1, 2details
#11--2details
#12ACCEPTED0.09 s2details
#130.09 s2details
#140.09 s2details
#15ACCEPTED0.00 s1, 2details
#160.00 s1, 2details
#170.00 s1, 2details
#180.00 s1, 2details
#190.00 s1, 2details
#200.00 s1, 2details
#210.09 s2details
#220.09 s2details
#230.09 s2details
#24ACCEPTED0.01 s1, 2details
#25ACCEPTED0.09 s2details
#26ACCEPTED0.00 s1, 2details
#27ACCEPTED0.09 s2details
#28ACCEPTED0.00 s1, 2details
#29ACCEPTED0.09 s2details
#30ACCEPTED0.00 s1, 2details
#31ACCEPTED0.09 s2details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:130:20: warning: 'root' may be used uninitialized [-Wmaybe-uninitialized]
  130 |     root->calc_down();
      |     ~~~~~~~~~~~~~~~^~

Code

#include <algorithm>
#include <cassert>
#include <chrono>
#include <climits>
#include <iostream>
#include <memory>
#include <numeric>
#include <sstream>
#include <thread>
#include <vector>
using ll = long long;
#undef assert
#define assert(x) \
do { \
if (!(x)) std::this_thread::sleep_for(std::chrono::seconds(10)); \
} while (0);
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"(7
// 1 1 0 0 1 1 1
// 1 2 20
// 2 3 30
// 2 5 50
// 3 6 60
// 1 4 10
// 6 7 100
// )" };
// 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 << sum << "\n";
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
1
0

correct output
0

user output
0

Test 2

Group: 1, 2

Verdict: ACCEPTED

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

correct output
0

user output
0

Test 3

Group: 1, 2

Verdict: ACCEPTED

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

correct output
60

user output
60

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
100

Test 5

Group: 1, 2

Verdict: ACCEPTED

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

correct output
6

user output
6

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)

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)

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)

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)

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)

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)

Test 12

Group: 2

Verdict: ACCEPTED

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

correct output
5683983203973

user output
5683983203973

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
100624178

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
46658

Test 15

Group: 1, 2

Verdict: ACCEPTED

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

correct output
126238345

user output
126238345

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
501273

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
49730

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
1585351

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
59491

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
484348

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
979212327

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
507838

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
99645007

Test 24

Group: 1, 2

Verdict: ACCEPTED

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

correct output
291990

user output
291990

Test 25

Group: 2

Verdict: ACCEPTED

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

correct output
59607954

user output
59607954

Test 26

Group: 1, 2

Verdict: ACCEPTED

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

correct output
990

user output
990

Test 27

Group: 2

Verdict: ACCEPTED

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

correct output
199982

user output
199982

Test 28

Group: 1, 2

Verdict: ACCEPTED

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

correct output
7987

user output
7987

Test 29

Group: 2

Verdict: ACCEPTED

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

correct output
3137875

user output
3137875

Test 30

Group: 1, 2

Verdict: ACCEPTED

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

correct output
4657693

user output
4657693

Test 31

Group: 2

Verdict: ACCEPTED

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

correct output
1652889357

user output
1652889357