CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:qanpi
Submission time:2022-11-09 21:59:53 +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.28 s2details
#8ACCEPTED0.01 s1, 2details
#9ACCEPTED0.28 s2details
#10ACCEPTED0.01 s1, 2details
#11ACCEPTED0.27 s2details
#12ACCEPTED0.23 s2details
#13ACCEPTED0.24 s2details
#14ACCEPTED0.23 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.22 s2details
#22ACCEPTED0.22 s2details
#23ACCEPTED0.23 s2details
#24ACCEPTED0.01 s1, 2details
#25ACCEPTED0.22 s2details
#26ACCEPTED0.01 s1, 2details
#27ACCEPTED0.21 s2details
#28ACCEPTED0.01 s1, 2details
#29ACCEPTED0.21 s2details
#30ACCEPTED0.01 s1, 2details
#31ACCEPTED0.22 s2details

Code

#include<iostream>
#include<vector>
using namespace std;
bool field[2*100000+1];
vector<pair<int, int>> adj[2*100000+1];
int down[2*100000+1];
int up[2*100000+1];
const int INF = 10e7;
void dfs(int s, int e);
void dfs2(int s, int e);
int calls = 0;
int main() {
cin.tie(0);
//freopen("harvest10.txt", "r", stdin);
int n;
cin >> n;
for (int i=1; i<=n; i++) {
cin >> field[i];
up[i] = INF;
}
for(int i=0; i<n-1; i++) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
long long int total_sum = 0;
dfs(1, 0);
dfs2(1, 0);
for (int i=1; i<=n; i++) {
if (field[i]) {
int res = min(down[i], up[i]);
//cout << i << " " << res << endl;
total_sum += res;
}
}
cout << total_sum << endl;
}
void dfs(int s, int e) {
if(field[s]) down[s] = INF;
for (auto u : adj[s]) {
int a = u.first, c = u.second;
if (a == e) continue;
dfs(a, s);
if (down[a] + c < down[s]) {
down[s] = down[a]+c;
// blacklist[s] = a;
}
}
//cout << s << " " << down[s] << endl;
}
//void other(int s, int e) {
// if(field[s]) down_2[s] = INF;
//
// for (auto u : adj[s]) {
// int a = u.first, c = u.second;
// if (a == e) continue;
// if (a == blacklist[s]) continue;
//
// dfs(a, s);
// down_2[s] = min(down_2[s], down[a] + c);
// }
// //cout << s << " " << down_2[s] << endl;
//}
void dfs2(int s, int e) {
if (!field[s]) up[s] = 0;
for (auto u : adj[s]) {
int a = u.first, c = u.second;
if (a == e) continue;
if (field[a]) up[a] = min(up[s] + c, down[s] + c);
dfs2(a, s);
}
//cout << s << " " << up[s] << endl;
}
//int dfs2(int s, int e) {
// if(!field[s]) return 0;
// if(memo2[s] != 0) return memo2[s];
//
// int shortest = INF;
// for (auto u : adj[s]) {
// int a = u.first, c = u.second;
// if (a == e) continue;
// if (a == blacklist[s]) continue;
//
// shortest = min(shortest, dfs2(a, s) + c);
// }
//
// memo2[s] = shortest;
// return shortest;
//}

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