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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i=0; i<n-harbors.size(); i++) {
      |                   ~^~~~~~~~~~~~~~~~~

Code

#include <climits>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
using tpl = tuple<int, int, ll>;
vector<int> visited;
class Compare {
public:
bool operator() (tpl a, tpl b) {return (get<2>(a) < get<2>(b) && !visited[get<1>(a)]) || visited[get<1>(b)];}
};
using pqueue = priority_queue<tpl, vector<tpl>, Compare>;
vector<int> harbors;
int n;
map<int, pqueue> reachableFrom;
map<int, vector<tpl>> network;
map<int,ll> roadLengths;
tpl next() {
ll m = LLONG_MAX;
map<int,pqueue>::iterator best;
for (auto it = reachableFrom.begin(); it!= reachableFrom.end(); it++) {
auto x = (it->second).top();
// ll t = get<2>((it->second).top());
while (visited[get<1>(x)]) {
(it->second).pop();
if ((it->second).empty())
break;
x = (it->second).top();
}
if (get<2>(x) < m && !visited[get<1>(x)]) {
m = get<2>(x);
best = it;
}
}
tpl return_val = (best->second).top();
(best->second).pop();
roadLengths[get<1>(return_val)] = get<2>(return_val);
for (auto x : network[get<1>(return_val)]) {
if (get<1>(x) != get<0>(return_val)) {
reachableFrom[best->first].push({get<0>(x), get<1>(x), roadLengths[get<0>(x)] + get<2>(x)});
}
}
return return_val;
}
int main() {
int a,b,t;
ll c;
cin >> n;
visited = vector<int>(n, 0);
for (int i=0; i<n; i++) {
cin >> t;
network[i] = vector<tpl>();
roadLengths[i] = 0;
if (t==0) {
harbors.push_back(i);
reachableFrom[i] = pqueue();
visited[i] = 1;
}
}
for (int i=0; i<n-1; i++) {
cin >> a >> b >> c; a--; b--;
network[a].push_back({a,b,c});
network[b].push_back({b,a,c});
if (reachableFrom.count(a)) {
reachableFrom[a].push({a,b,c});}
if (reachableFrom.count(b)) {
reachableFrom[b].push({b,a,c});}
}
tpl T;
ll total = 0;
for (int i=0; i<n-harbors.size(); i++) {
T = next();
visited[get<1>(T)] = 1;
}
for (int i=0; i<n; i++) {
total += roadLengths[i];
}
cout << total;
}

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:

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

correct output
6

user output
(empty)

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:

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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