Task: | Sadonkorjuu |
Sender: | Ihminen |
Submission time: | 2022-12-05 20:25:54 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 33 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 33 |
#2 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | ACCEPTED | 0.00 s | 1, 2 | details |
#3 | ACCEPTED | 0.00 s | 1, 2 | details |
#4 | ACCEPTED | 0.00 s | 1, 2 | details |
#5 | ACCEPTED | 0.00 s | 1, 2 | details |
#6 | ACCEPTED | 0.10 s | 1, 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | ACCEPTED | 0.05 s | 1, 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | ACCEPTED | 0.01 s | 1, 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 2 | details |
#12 | TIME LIMIT EXCEEDED | -- | 2 | details |
#13 | TIME LIMIT EXCEEDED | -- | 2 | details |
#14 | ACCEPTED | 0.82 s | 2 | details |
#15 | ACCEPTED | 0.03 s | 1, 2 | details |
#16 | ACCEPTED | 0.02 s | 1, 2 | details |
#17 | ACCEPTED | 0.01 s | 1, 2 | details |
#18 | ACCEPTED | 0.08 s | 1, 2 | details |
#19 | ACCEPTED | 0.01 s | 1, 2 | details |
#20 | ACCEPTED | 0.05 s | 1, 2 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2 | details |
#22 | TIME LIMIT EXCEEDED | -- | 2 | details |
#23 | TIME LIMIT EXCEEDED | -- | 2 | details |
#24 | ACCEPTED | 0.05 s | 1, 2 | details |
#25 | TIME LIMIT EXCEEDED | -- | 2 | details |
#26 | ACCEPTED | 0.03 s | 1, 2 | details |
#27 | TIME LIMIT EXCEEDED | -- | 2 | details |
#28 | ACCEPTED | 0.05 s | 1, 2 | details |
#29 | TIME LIMIT EXCEEDED | -- | 2 | details |
#30 | ACCEPTED | 0.09 s | 1, 2 | details |
#31 | TIME LIMIT EXCEEDED | -- | 2 | details |
Code
#include <iostream>#include <vector>#include <queue>using namespace std;// Edge class that represents an edge in the graphclass Edge{public:int to; // The index of the node that this edge leads toint cost; // The cost of traveling along this edge// Constructor to initialize the edgeEdge(int to, int cost) : to(to), cost(cost) {}};// Graph class that represents a graph with nodes and edgesclass Graph{public:vector<vector<Edge>> edges; // Adjacency list that stores the edges for each node// Constructor to initialize the graph with n nodesGraph(int n) : edges(n) {}// Adds a new edge to the graph from node u to node v with the given costvoid 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 algorithmvoid dijkstra(const Graph& graph, vector<int>& distances, int source){// Initialize distances to all nodes as infiniteint n = graph.edges.size();distances.assign(n, -1);// Create a priority queue to store the nodes that need to be processedauto 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 0distances[source] = 0;pq.push({ 0, source });// Process nodes in the priority queue until it is emptywhile (!pq.empty()){// Get the node with the smallest distanceint u = pq.top().second;pq.pop();// Iterate through the edges of the nodefor (Edge edge : graph.edges[u]){// Calculate the new distance to the adjacent nodeint v = edge.to;int new_distance = distances[u] + edge.cost;// If the new distance is smaller than the current distance, update the distanceif (distances[v] == -1 || new_distance < distances[v]){distances[v] = new_distance;pq.push({ new_distance, v });}}}}int main(){int n;// Read the number of citiescin >> n;// Read the type of each cityvector<int> city_types(n);for (int& type : city_types)cin >> type;// Create a graph with n nodesGraph graph(n);// Read the roads and add them to the graphfor (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 portsvector<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 portint total_distance = 0;for (int field : sunflower_fields){// Calculate the shortest distances from the current sunflower field to all nodes in the graphvector<int> distances;dijkstra(graph, distances, field);// Find the port that is closest to the current sunflower fieldint 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 distancetotal_distance += min_distance;}// Print the total distancecout << 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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
200000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1652889357 |
user output |
---|
(empty) |