Task: | Sadonkorjuu |
Sender: | Sup |
Submission time: | 2022-11-13 23:49:49 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#3 | ACCEPTED | 0.00 s | 1, 2 | details |
#4 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#5 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#6 | ACCEPTED | 0.01 s | 1, 2 | details |
#7 | ACCEPTED | 0.35 s | 2 | details |
#8 | WRONG ANSWER | 0.06 s | 1, 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | WRONG ANSWER | 0.11 s | 1, 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 2 | details |
#12 | WRONG ANSWER | 0.27 s | 2 | details |
#13 | TIME LIMIT EXCEEDED | -- | 2 | details |
#14 | TIME LIMIT EXCEEDED | -- | 2 | details |
#15 | ACCEPTED | 0.01 s | 1, 2 | details |
#16 | WRONG ANSWER | 0.02 s | 1, 2 | details |
#17 | WRONG ANSWER | 0.03 s | 1, 2 | details |
#18 | WRONG ANSWER | 0.01 s | 1, 2 | details |
#19 | WRONG ANSWER | 0.09 s | 1, 2 | details |
#20 | WRONG ANSWER | 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 | WRONG ANSWER | 0.05 s | 1, 2 | details |
#25 | TIME LIMIT EXCEEDED | -- | 2 | details |
#26 | WRONG ANSWER | 0.03 s | 1, 2 | details |
#27 | TIME LIMIT EXCEEDED | -- | 2 | details |
#28 | ACCEPTED | 0.01 s | 1, 2 | details |
#29 | ACCEPTED | 0.28 s | 2 | details |
#30 | ACCEPTED | 0.01 s | 1, 2 | details |
#31 | ACCEPTED | 0.33 s | 2 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:199:13: warning: unused variable 'minDist' [-Wunused-variable] 199 | int minDist = INF; | ^~~~~~~ input/code.cpp:200:13: warning: unused variable 'distance' [-Wunused-variable] 200 | int distance; | ^~~~~~~~
Code
#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 svector<int> 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 verticesvector<int> 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]);*/return dist;}// 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;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_ports.push_back(k);}if (city_identity_number == 0){the_list_for_farms.push_back(k);}}//cout << "the first loop is done" << endl;for (int i = 0; i < amount_of_paths; i++){for (int j = 0; j < 3; j++){cin >> distance_between_2_cities;if (j == 0){starting_vertex = distance_between_2_cities-1;//the_list_for_farms.insert(distance_between_2_cities)}if (j == 1){end_vertex = distance_between_2_cities-1;//the_list_for_ports.insert(distance_between_2_cities)}if (j == 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 callvector<int> list_of_distances;vector<int> list_for_port_distances;int shortest_path = 0;for (auto i : the_list_for_farms){//cout << i << endl;list_of_distances = g.shortestPath(i);int minDist = INF;int distance;/*for (auto l : the_list_for_ports){distance = list_of_distances[l];if(distance < minDist){minDist = distance;}//list_for_port_distances.push_back(list_of_distances[l])}*/if (list_for_port_distances.size() == 0) {list_for_port_distances = list_of_distances;}//list_for_port_distances.push_back(list_of_distances[i])if (list_for_port_distances.size() != 0) {for (int ii = 0; ii < amount_of_paths; ii++){if (list_for_port_distances[ii] > list_of_distances[ii]){list_for_port_distances[ii] = list_of_distances[ii];}}}}for (auto jj : list_for_port_distances){shortest_path += jj;}cout << shortest_path << endl;//g.shortestPath(0);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: WRONG ANSWER
input |
---|
5 0 0 0 0 0 1 2 1 2 3 2 3 4 3 ... |
correct output |
---|
0 |
user output |
---|
10 |
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: WRONG ANSWER
input |
---|
5 0 1 1 1 0 1 2 10 2 3 20 3 4 30 ... |
correct output |
---|
80 |
user output |
---|
180 |
Test 5
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
5 0 1 0 1 1 1 2 1 2 3 5 3 4 3 ... |
correct output |
---|
6 |
user output |
---|
12 |
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: ACCEPTED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1795118520 |
user output |
---|
1795118520 |
Test 8
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 ... |
correct output |
---|
293576 |
user output |
---|
294796 |
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: WRONG ANSWER
input |
---|
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
3089 |
user output |
---|
5464 |
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: WRONG ANSWER
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: 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: 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: WRONG ANSWER
input |
---|
1000 0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 ... |
correct output |
---|
278678 |
user output |
---|
772042 |
Test 17
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 ... |
correct output |
---|
34929 |
user output |
---|
526082 |
Test 18
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1543963 |
user output |
---|
1549125 |
Test 19
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
39606 |
user output |
---|
44295 |
Test 20
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 ... |
correct output |
---|
321598 |
user output |
---|
326281 |
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: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
291990 |
user output |
---|
295263 |
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: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
990 |
user output |
---|
995 |
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: 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 |