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

Compiler report

input/code.cpp: In function 'void dijkstra()':
input/code.cpp:36:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         auto [len, v] = *d.begin();
      |              ^
input/code.cpp:40:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         for (auto [u, w] : g[v]) {
      |                   ^

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <numeric>
#include <random>
#include <chrono>
#include <ctime>
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
const int INF = 1e18;
int n;
vector<bool> c;
vector<int> dist;
vector<vector<pair<int, int>>> g;
void init() {
c.resize(n);
dist.assign(n, INF);
g.assign(n, {});
}
void dijkstra() {
set<pair<int, int>> d;
for (int i = 0; i < n; ++i) {
if (c[i]) {
d.emplace(0, i);
}
}
while (!d.empty()) {
auto [len, v] = *d.begin();
d.erase(*d.begin());
if (dist[v] != INF) continue;
dist[v] = len;
for (auto [u, w] : g[v]) {
if (dist[u] == INF) {
d.emplace(len + w, u);
}
}
}
}
signed main() {
//freopen("file.in", "r", stdin);
//freopen("file.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(20);
cout.setf(ios::fixed);
cin >> n;
init();
for (int i = 0; i < n; ++i) {
int x; cin >> x;
c[i] = !x;
}
for (int i = 0; i < n - 1; ++i) {
int u, v, w; cin >> u >> v >> w;
--u;
--v;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
dijkstra();
int ans = 0;
for (int i = 0; i < n; ++i) {
if (!c[i]) ans += dist[i];
}
cout << ans << endl;
return 0;
}

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