CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Yamaxanadu
Submission time:2022-11-07 12:57:24 +0200
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED33
#2ACCEPTED67
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.01 s1, 2details
#3ACCEPTED0.01 s1, 2details
#4ACCEPTED0.01 s1, 2details
#5ACCEPTED0.01 s1, 2details
#6ACCEPTED0.01 s1, 2details
#7ACCEPTED0.30 s2details
#8ACCEPTED0.01 s1, 2details
#9ACCEPTED0.31 s2details
#10ACCEPTED0.01 s1, 2details
#11ACCEPTED0.31 s2details
#12ACCEPTED0.26 s2details
#13ACCEPTED0.26 s2details
#14ACCEPTED0.26 s2details
#15ACCEPTED0.01 s1, 2details
#16ACCEPTED0.01 s1, 2details
#17ACCEPTED0.01 s1, 2details
#18ACCEPTED0.01 s1, 2details
#19ACCEPTED0.01 s1, 2details
#20ACCEPTED0.01 s1, 2details
#21ACCEPTED0.24 s2details
#22ACCEPTED0.25 s2details
#23ACCEPTED0.25 s2details
#24ACCEPTED0.01 s1, 2details
#25ACCEPTED0.25 s2details
#26ACCEPTED0.01 s1, 2details
#27ACCEPTED0.23 s2details
#28ACCEPTED0.01 s1, 2details
#29ACCEPTED0.23 s2details
#30ACCEPTED0.01 s1, 2details
#31ACCEPTED0.24 s2details

Compiler report

input/code.cpp: In function 'void search(int, int, int, int)':
input/code.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < v[f].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
input/code.cpp: In function 'void sec_search(int, int, int)':
input/code.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < v[f].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int i = 0; i < todo.size(); i++) {
      |...

Code

#include <bits/stdc++.h>
using namespace std;
long long ans;
vector<pair<int,int>> v[200001];
vector<int> s;
vector<pair<int,pair<int,int>>> x;
vector<int> todo;
vector<int> todon;
int n, a, b, c, d, fp, fpb, done;
void search(int f, int g, int h, int hl) {
if (s[f-1] == 0) {
h = 0;
if (f != fp) {
todo.push_back(f);
}
}
x[f].first = min(x[f].first,h);
x[f].second.first = g;
x[f].second.second = hl;
for (int i = 0; i < v[f].size(); i++) {
if (v[f][i].first != g) {
search(v[f][i].first, f, h+v[f][i].second,v[f][i].second);
}
}
}
void sec_search(int f, int g, int h) {
x[f].first = min(x[f].first,h+x[f].second.second);
for (int i = 0; i < v[f].size(); i++) {
if (v[f][i].first != g) {
sec_search(v[f][i].first, f, x[f].first);
}
}
}
int main() {
done = 0;
ans = 0;
fp = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a;
s.push_back(a);
if (fpb == 0 and a == 0) {
fp = i;
fpb = 1;
}
}
for (int i = 0; i <= n; i++) {
x.push_back({1000000000,{100,100}});
}
for (int i = 1; i < n; i++) {
cin >> b >> c >> d;
v[b].push_back({c,d});
v[c].push_back({b,d});
}
search(fp,0,0,0);
while (done == 0) {
for (int i = 0; i < todo.size(); i++) {
if (x[x[todo[i]].second.first].first > x[todo[i]].first+x[todo[i]].second.second) {
x[x[todo[i]].second.first].first = x[todo[i]].first+x[todo[i]].second.second;
todon.push_back(x[todo[i]].second.first);
}
}
todo = todon;
todon = {};
if (todo.size() == 0) {
done = 1;
}
}
sec_search(fp,0,0);
for (int i = 1; i <= n; i++) {
ans = (long long)ans+x[i].first;
}
cout << ans;
}

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

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

correct output
80

user output
80

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

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

correct output
5506363

user output
5506363

Test 7

Group: 2

Verdict: ACCEPTED

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

correct output
1795118520

user output
1795118520

Test 8

Group: 1, 2

Verdict: ACCEPTED

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

correct output
293576

user output
293576

Test 9

Group: 2

Verdict: ACCEPTED

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

correct output
816932444

user output
816932444

Test 10

Group: 1, 2

Verdict: ACCEPTED

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

correct output
3089

user output
3089

Test 11

Group: 2

Verdict: ACCEPTED

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

correct output
40839

user output
40839

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

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

correct output
58572993

user output
58572993

Test 14

Group: 2

Verdict: ACCEPTED

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

correct output
32755

user output
32755

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

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

correct output
278678

user output
278678

Test 17

Group: 1, 2

Verdict: ACCEPTED

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

correct output
34929

user output
34929

Test 18

Group: 1, 2

Verdict: ACCEPTED

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

correct output
1543963

user output
1543963

Test 19

Group: 1, 2

Verdict: ACCEPTED

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

correct output
39606

user output
39606

Test 20

Group: 1, 2

Verdict: ACCEPTED

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

correct output
321598

user output
321598

Test 21

Group: 2

Verdict: ACCEPTED

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

correct output
978670626

user output
978670626

Test 22

Group: 2

Verdict: ACCEPTED

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

correct output
375218

user output
375218

Test 23

Group: 2

Verdict: ACCEPTED

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

correct output
60422556

user output
60422556

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