CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:FenixHongell
Submission time:2022-11-09 08:59:47 +0200
Language:C++ (C++11)
Status:READY
Result:33
Feedback
groupverdictscore
#1ACCEPTED33
#20
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#2ACCEPTED0.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#4ACCEPTED0.00 s1, 2details
#5ACCEPTED0.00 s1, 2details
#6ACCEPTED0.01 s1, 2details
#7--2details
#8ACCEPTED0.01 s1, 2details
#9--2details
#10ACCEPTED0.01 s1, 2details
#11--2details
#120.61 s2details
#13ACCEPTED0.96 s2details
#14ACCEPTED0.82 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.96 s2details
#22ACCEPTED0.82 s2details
#23ACCEPTED0.96 s2details
#24ACCEPTED0.01 s1, 2details
#25ACCEPTED0.95 s2details
#26ACCEPTED0.01 s1, 2details
#27ACCEPTED0.72 s2details
#28ACCEPTED0.01 s1, 2details
#29ACCEPTED0.64 s2details
#30ACCEPTED0.01 s1, 2details
#31ACCEPTED0.97 s2details

Code

#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <climits>
#include <regex>
#include <numeric>
#include <algorithm>
using namespace std;
template<typename T>
class Graph {
map<T, list<pair<T, unsigned int>>> l;
public:
void addEdge(T x, T y,unsigned int wt) {
l[x].push_back({ y, wt });
l[y].push_back({ x, wt });
}
void djikstraSSSP(T src, vector<unsigned int>& scores) {
map<T, unsigned int> dist;
for (auto p : l) {
T node = p.first;
dist[node] = INT_MAX;
}
dist[src] = 0;
set<pair<unsigned int, T>> s;
s.insert({ dist[src], src });
while (!s.empty()) {
pair<unsigned int, T> p = *s.begin();
s.erase(s.begin());
T currNode = p.second;
int currNodeDist = p.first;
for (auto nbr : l[currNode]) {
T nbrNode = nbr.first;
int distInBetween = nbr.second;
int nbrNodeDist = dist[nbrNode];
if (currNodeDist + distInBetween < nbrNodeDist) {
auto pr = s.find({ dist[nbrNode], nbrNode });
if (pr != s.end()) {
s.erase(pr);
}
dist[nbrNode] = currNodeDist + distInBetween;
s.insert({ dist[nbrNode], nbrNode });
}
}
}
unsigned int i = 0;
for (auto x : dist) {
if (scores[i] != 0) {
if (scores[i] > x.second) {
scores[i] = x.second;
}
}
else {
scores[i] = x.second;
}
++i;
}
}
};
int main() {
Graph<unsigned int> g;
register unsigned int V = 0;
cin >> V;
register unsigned int i = 0;
register unsigned int paths = V - 1;
string roles;
getline(cin >> ws, roles);
std::regex r("\\s+");
roles = std::regex_replace(roles, r, "");
while (i < paths) {
register unsigned int a, b, c;
cin >> a >> b >> c;
g.addEdge(a, b, c);
++i;
}
register unsigned int j = 1;
std::string::difference_type rl = std::count(roles.begin(), roles.end(), '0');
while (j < roles.length() + 1) {
if (roles[j - 1] == '0') {
g.addEdge(0, j, 0);
}
++j;
}
vector<unsigned int> scores(V + rl, 0);
g.djikstraSSSP(0, scores);
int totalLength = std::accumulate(scores.begin(), scores.end(), 0);
std::cout << totalLength << endl;
}

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:

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

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

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:

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

correct output
5683983203973

user output
1741471365

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