Task: | Sadonkorjuu |
Sender: | Ihminen |
Submission time: | 2022-12-05 21:27:27 +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.02 s | 1, 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | ACCEPTED | 0.01 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.56 s | 2 | details |
#15 | ACCEPTED | 0.01 s | 1, 2 | details |
#16 | ACCEPTED | 0.01 s | 1, 2 | details |
#17 | ACCEPTED | 0.01 s | 1, 2 | details |
#18 | ACCEPTED | 0.01 s | 1, 2 | details |
#19 | ACCEPTED | 0.01 s | 1, 2 | details |
#20 | ACCEPTED | 0.01 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.01 s | 1, 2 | details |
#25 | TIME LIMIT EXCEEDED | -- | 2 | details |
#26 | ACCEPTED | 0.01 s | 1, 2 | details |
#27 | TIME LIMIT EXCEEDED | -- | 2 | details |
#28 | ACCEPTED | 0.01 s | 1, 2 | details |
#29 | TIME LIMIT EXCEEDED | -- | 2 | details |
#30 | ACCEPTED | 0.01 s | 1, 2 | details |
#31 | TIME LIMIT EXCEEDED | -- | 2 | details |
Compiler report
input/code.cpp: In function 'void bfs(const Graph&, int*, int)': input/code.cpp:43:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation] 43 | for (int i = 0; i < n; i++) | ^~~ input/code.cpp:47:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for' 47 | deque<int> q; | ^~~~~
Code
#include <iostream>#include <deque>#include <unordered_set>#include<vector>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 breadth-first searchvoid bfs(const Graph& graph, int* distances, int source){// Initialize distances to all nodes as infiniteint n = graph.edges.size();for (int i = 0; i < n; i++)distances[i] = -1;// Create a deque to store the nodes that need to be processeddeque<int> q;// Add the source node to the deque with distance 0distances[source] = 0;q.push_back(source);// Process nodes in the deque until it is emptywhile (!q.empty()){// Get the next node in the dequeint u = q.front();q.pop_front();// Iterate throughfor (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;q.push_back(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 portsunordered_set<int> sunflower_fields;unordered_set<int> ports;for (int i = 0; i < n; i++){if (city_types[i] == 0)ports.insert(i);else if (city_types[i] == 1)sunflower_fields.insert(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 graphint* distances = new int[n];bfs(graph, distances, field);// Find the port with the smallest distance to the sunflower fieldint min_distance = -1;for (int port : ports){if (distances[port] != -1 && (min_distance == -1 || distances[port] < min_distance))min_distance = distances[port];}// Add the distance to the total distancetotal_distance += min_distance;// Free the memory used by the arraydelete[] distances;}// 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) |