CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Ihminen
Submission time:2022-12-05 20:25:54 +0200
Language:C++ (C++17)
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.10 s1, 2details
#7--2details
#8ACCEPTED0.05 s1, 2details
#9--2details
#10ACCEPTED0.01 s1, 2details
#11--2details
#12--2details
#13--2details
#14ACCEPTED0.82 s2details
#15ACCEPTED0.03 s1, 2details
#16ACCEPTED0.02 s1, 2details
#17ACCEPTED0.01 s1, 2details
#18ACCEPTED0.08 s1, 2details
#19ACCEPTED0.01 s1, 2details
#20ACCEPTED0.05 s1, 2details
#21--2details
#22--2details
#23--2details
#24ACCEPTED0.05 s1, 2details
#25--2details
#26ACCEPTED0.03 s1, 2details
#27--2details
#28ACCEPTED0.05 s1, 2details
#29--2details
#30ACCEPTED0.09 s1, 2details
#31--2details

Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Edge class that represents an edge in the graph
class Edge
{
public:
int to; // The index of the node that this edge leads to
int cost; // The cost of traveling along this edge
// Constructor to initialize the edge
Edge(int to, int cost) : to(to), cost(cost) {}
};
// Graph class that represents a graph with nodes and edges
class Graph
{
public:
vector<vector<Edge>> edges; // Adjacency list that stores the edges for each node
// Constructor to initialize the graph with n nodes
Graph(int n) : edges(n) {}
// Adds a new edge to the graph from node u to node v with the given cost
void addEdge(int u, int v, int cost)
{
edges[u].push_back(Edge(v, cost));
edges[v].push_back(Edge(u, cost));
}
};
// A utility function to find the shortest distances from the source node to all other nodes in the graph
// using Dijkstra's algorithm
void dijkstra(const Graph& graph, vector<int>& distances, int source)
{
// Initialize distances to all nodes as infinite
int n = graph.edges.size();
distances.assign(n, -1);
// Create a priority queue to store the nodes that need to be processed
auto cmp = [](pair<int, int>& a, pair<int, int>& b) { return a.first > b.first; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
// Add the source node to the priority queue with distance 0
distances[source] = 0;
pq.push({ 0, source });
// Process nodes in the priority queue until it is empty
while (!pq.empty())
{
// Get the node with the smallest distance
int u = pq.top().second;
pq.pop();
// Iterate through the edges of the node
for (Edge edge : graph.edges[u])
{
// Calculate the new distance to the adjacent node
int v = edge.to;
int new_distance = distances[u] + edge.cost;
// If the new distance is smaller than the current distance, update the distance
if (distances[v] == -1 || new_distance < distances[v])
{
distances[v] = new_distance;
pq.push({ new_distance, v });
}
}
}
}
int main()
{
int n;
// Read the number of cities
cin >> n;
// Read the type of each city
vector<int> city_types(n);
for (int& type : city_types)
cin >> type;
// Create a graph with n nodes
Graph graph(n);
// Read the roads and add them to the graph
for (int i = 0; i < n - 1; i++)
{
int u, v, cost;
cin >> u >> v >> cost;
graph.addEdge(u - 1, v - 1, cost);
}
// Find the indices of the sunflower fields and ports
vector<int> sunflower_fields;
vector<int> ports;
for (int i = 0; i < n; i++)
{
if (city_types[i] == 0)
ports.push_back(i);
else if (city_types[i] == 1)
sunflower_fields.push_back(i);
}
// Calculate the shortest distance from each sunflower field to a port
int total_distance = 0;
for (int field : sunflower_fields)
{
// Calculate the shortest distances from the current sunflower field to all nodes in the graph
vector<int> distances;
dijkstra(graph, distances, field);
// Find the port that is closest to the current sunflower field
int min_distance = -1;
for (int port : ports)
{
if (min_distance == -1 || distances[port] < min_distance)
min_distance = distances[port];
}
// Add the distance to the total distance
total_distance += min_distance;
}
// Print the total distance
cout << total_distance << 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:

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

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

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

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

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:

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

correct output
3137875

user output
(empty)

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:

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

correct output
1652889357

user output
(empty)