Task: | Sadonkorjuu |
Sender: | Sup |
Submission time: | 2023-09-03 19:19:33 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#2 | WRONG ANSWER | 0.17 s | 1, 2 | details |
#3 | RUNTIME ERROR | 0.00 s | 1, 2 | details |
#4 | RUNTIME ERROR | 0.00 s | 1, 2 | details |
#5 | RUNTIME ERROR | 0.00 s | 1, 2 | details |
#6 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 2 | details |
#12 | TIME LIMIT EXCEEDED | -- | 2 | details |
#13 | TIME LIMIT EXCEEDED | -- | 2 | details |
#14 | TIME LIMIT EXCEEDED | -- | 2 | details |
#15 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#16 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#17 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#18 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#19 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#20 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2 | details |
#22 | TIME LIMIT EXCEEDED | -- | 2 | details |
#23 | TIME LIMIT EXCEEDED | -- | 2 | details |
#24 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#25 | TIME LIMIT EXCEEDED | -- | 2 | details |
#26 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#27 | TIME LIMIT EXCEEDED | -- | 2 | details |
#28 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#29 | TIME LIMIT EXCEEDED | -- | 2 | details |
#30 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#31 | TIME LIMIT EXCEEDED | -- | 2 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:157:18: warning: 'the_distance' may be used uninitialized in this function [-Wmaybe-uninitialized] 157 | g.addEdge(starting_vertex, end_vertex, the_distance); | ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ input/code.cpp:157:18: warning: 'end_vertex' may be used uninitialized in this function [-Wmaybe-uninitialized] input/code.cpp:157:18: warning: 'starting_vertex' may be used uninitialized in this function [-Wmaybe-uninitialized]
Code
// C++ Program to find Dijkstra's shortest path using// priority_queue in STL#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#include<list>// iPair ==> Integer Pairtypedef pair<int, int> iPair;// This class represents a directed graph using// adjacency list representationclass Graph {int V; // No. of vertices// In a weighted graph, we need to store vertex// and weight pair for every edgelist<pair<int, int> >* adj;public:Graph(int V); // Constructor// ction to add an edge to graphvoid addEdge(int u, int v, int w);// prints shortest path from svoid shortestPath(int s);};// Allocates memory for adjacency listGraph::Graph(int V){this->V = V;adj = new list<iPair>[V];}void Graph::addEdge(int u, int v, int w){adj[u].push_back(make_pair(v, w));adj[v].push_back(make_pair(u, w));}// Prints shortest paths from src to all other verticesvoid Graph::shortestPath(int src){// Create a priority queue to store vertices that// are being preprocessed. This is weird syntax in C++.// Refer below link for details of this syntax// https://www.geeksforgeeks.org/implement-min-heap-using-stl/priority_queue<iPair, vector<iPair>, greater<iPair> >pq;// Create a vector for distances and initialize all// distances as infinite (INF)vector<int> dist(V, INF);// Insert source itself in priority queue and initialize// its distance as 0.pq.push(make_pair(0, src));dist[src] = 0;/* Looping till priority queue becomes empty (or alldistances are not finalized) */while (!pq.empty()) {// The first vertex in pair is the minimum distance// vertex, extract it from priority queue.// vertex label is stored in second of pair (it// has to be done this way to keep the vertices// sorted distance (distance must be first item// in pair)int u = pq.top().second;pq.pop();// 'i' is used to get all adjacent vertices of a// vertexlist<pair<int, int> >::iterator i;for (i = adj[u].begin(); i != adj[u].end(); ++i) {// Get vertex label and weight of current// adjacent of u.int v = (*i).first;int weight = (*i).second;// If there is shorted path to v through u.if (dist[v] > dist[u] + weight) {// Updating distance of vdist[v] = dist[u] + weight;pq.push(make_pair(dist[v], v));}}}// Print shortest distances stored in dist[]//printf("Vertex Distance from Source\n");for (int i = 0; i < V; ++i)printf("%d \t\t %d\n", i, dist[i]);}// Driver's codeint main(){int amount_of_cities; //gets the number of cities that we will have as inputint amount_of_paths; // we calculate the amount of path between the cities, which is (amount_of_cities-1)int city_identity_number;list<int> city_identifier = {}; // this is the list in which we store the value of 1 and 0 that identifies, if the city has a port or a farm.list<int> the_list_for_farms = {}; // this is the list that will keep all of the verteces, with the value 1.list<int> the_list_for_ports = {}; // this is the list that will keep all the verteces with the value 0.list<int> the_ordinal_number_of_vertex = {};int distance_between_2_cities; // the rows of input that we will get, basically the distance between 2 points.int starting_vertex;int end_vertex;int the_distance;ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> amount_of_cities; //input to see how many verteces we will have.amount_of_paths = amount_of_cities - 1;//int array_of_distances[]Graph g(amount_of_cities);for (int k = 0; k < amount_of_cities; k++){cin >> city_identity_number;city_identifier.push_back(city_identity_number);if (city_identity_number == 1){the_list_for_farms.push_back(k);}if (city_identity_number == 0){the_list_for_ports.push_back(k);}}for (int i = 0; i < amount_of_paths; i++){for (int j = 0; j < 3; j++){cin >> distance_between_2_cities;if (i == 0){starting_vertex = distance_between_2_cities;//the_list_for_farms.insert(distance_between_2_cities)}if (i == 1){end_vertex = distance_between_2_cities;//the_list_for_ports.insert(distance_between_2_cities)}if (i == 2){the_distance = distance_between_2_cities;}g.addEdge(starting_vertex, end_vertex, the_distance);}}// create the graph given in above figure//int V = 9;//Graph g(V);// making above shown graph/*g.addEdge(0, 1, 4);g.addEdge(0, 7, 8);g.addEdge(1, 2, 8);g.addEdge(1, 7, 11);g.addEdge(2, 3, 7);g.addEdge(2, 8, 2);g.addEdge(2, 5, 4);g.addEdge(3, 4, 9);g.addEdge(3, 5, 14);g.addEdge(4, 5, 10);g.addEdge(5, 6, 2);g.addEdge(6, 7, 1);g.addEdge(6, 8, 6);g.addEdge(7, 8, 7);*/// Function callg.shortestPath(0);return 0;}
Test details
Test 1
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1 0 |
correct output |
---|
0 |
user output |
---|
0 0 |
Test 2
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
5 0 0 0 0 0 1 2 1 2 3 2 3 4 3 ... |
correct output |
---|
0 |
user output |
---|
0 -2147480800 1 -2147480797 2 -2147480800 3 -2147480800 4 1061109567 |
Test 3
Group: 1, 2
Verdict: RUNTIME ERROR
input |
---|
4 1 0 1 1 1 2 10 2 3 20 2 4 30 |
correct output |
---|
60 |
user output |
---|
(empty) |
Test 4
Group: 1, 2
Verdict: RUNTIME ERROR
input |
---|
5 0 1 1 1 0 1 2 10 2 3 20 3 4 30 ... |
correct output |
---|
80 |
user output |
---|
(empty) |
Test 5
Group: 1, 2
Verdict: RUNTIME ERROR
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: TIME LIMIT EXCEEDED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
5506363 |
user output |
---|
(empty) |
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: TIME LIMIT EXCEEDED
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: 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: TIME LIMIT EXCEEDED
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: 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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
126238345 |
user output |
---|
(empty) |
Test 16
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: 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: TIME LIMIT EXCEEDED
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: 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: TIME LIMIT EXCEEDED
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: 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: TIME LIMIT EXCEEDED
input |
---|
1000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
7987 |
user output |
---|
(empty) |
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: TIME LIMIT EXCEEDED
input |
---|
1000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
4657693 |
user output |
---|
(empty) |
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) |