CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Sup
Submission time:2022-11-13 23:49:49 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#20.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#40.00 s1, 2details
#50.00 s1, 2details
#6ACCEPTED0.01 s1, 2details
#7ACCEPTED0.35 s2details
#80.06 s1, 2details
#9--2details
#100.11 s1, 2details
#11--2details
#120.27 s2details
#13--2details
#14--2details
#15ACCEPTED0.01 s1, 2details
#160.02 s1, 2details
#170.03 s1, 2details
#180.01 s1, 2details
#190.09 s1, 2details
#200.05 s1, 2details
#21--2details
#22--2details
#23--2details
#240.05 s1, 2details
#25--2details
#260.03 s1, 2details
#27--2details
#28ACCEPTED0.01 s1, 2details
#29ACCEPTED0.28 s2details
#30ACCEPTED0.01 s1, 2details
#31ACCEPTED0.33 s2details

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 Pair
typedef pair<int, int> iPair;
// This class represents a directed graph using
// adjacency list representation
class Graph {
int V; // No. of vertices
// In a weighted graph, we need to store vertex
// and weight pair for every edge
list<pair<int, int> >* adj;
public:
Graph(int V); // Constructor
// ction to add an edge to graph
void addEdge(int u, int v, int w);
// prints shortest path from s
vector<int> shortestPath(int s);
};
// Allocates memory for adjacency list
Graph::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 vertices
vector<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 all
distances 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
// vertex
list<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 v
dist[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 code
int main()
{
int amount_of_cities; //gets the number of cities that we will have as input
int 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 call
vector<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:

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:

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:

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:

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:

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:

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:

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
1741471365

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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