CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Sup
Submission time:2022-11-13 23:00:48 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#2ACCEPTED0.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#4ACCEPTED0.00 s1, 2details
#5ACCEPTED0.00 s1, 2details
#6--1, 2details
#70.05 s2details
#8--1, 2details
#90.05 s2details
#10--1, 2details
#110.05 s2details
#120.06 s2details
#130.06 s2details
#140.06 s2details
#15ACCEPTED0.93 s1, 2details
#16--1, 2details
#17--1, 2details
#18--1, 2details
#19--1, 2details
#20--1, 2details
#210.06 s2details
#220.06 s2details
#230.06 s2details
#24--1, 2details
#250.06 s2details
#26--1, 2details
#270.06 s2details
#28ACCEPTED0.12 s1, 2details
#290.06 s2details
#30ACCEPTED0.22 s1, 2details
#310.06 s2details

Compiler report

input/code.cpp: In function 'void create_graph()':
input/code.cpp:24:13: warning: unused variable 'i' [-Wunused-variable]
   24 |         int i, amount_of_paths, starting_vertex, end_vertex, the_distance, distance_between_2_cities;
      |             ^
input/code.cpp: At global scope:
input/code.cpp:146:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  146 | main()
      | ^~~~
input/code.cpp: In function 'int main()':
input/code.cpp:148:13: warning: unused variable 'i' [-Wunused-variable]
  148 |         int i, j;
      |             ^
input/code.cpp:148:16: warning: unused variable 'j' [-Wunused-variable]
  148 |         int i, j;
      |                ^
input/code.cpp:149:13: warning: unused variable 'source' [-Wunused-variable]
  149 |         int source, dest;
      |             ^~~~~~
input/code.cpp:149:21: warning: unused variable 'dest' [-Wunused-variable]
  149 |         int source, dest;
      |                     ^~~~
input/code.cpp:151:13:...

Code

#include<stdio.h>
#define MAX 1200
#define TEMP 0
#define PERM 1
#define INF 0x3f3f3f3f
#include<list>
using namespace std;
#include <bits/stdc++.h>
struct node
{
int predecessor;
int dist; /*minimum distance of node from source*/
int status;
};
int adj[MAX][MAX];
int n;
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.
void create_graph()
{
int i, amount_of_paths, starting_vertex, end_vertex, the_distance, distance_between_2_cities;
int city_identity_number;
cin >> n; // amount_of_cities; //input to see how many verteces we will have.
amount_of_paths = n - 1;
for (int k = 1; k <= n; 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);
}
}
// amount_of_paths = n - 1;
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;
//the_list_for_farms.insert(distance_between_2_cities)
}
if (j == 1) {
end_vertex = distance_between_2_cities;
//the_list_for_ports.insert(distance_between_2_cities)
}
if (j == 2) {
the_distance = distance_between_2_cities;
}
}
adj[starting_vertex][end_vertex] = the_distance;
adj[end_vertex][starting_vertex] = the_distance;
// cout<<adj[starting_vertex][end_vertex]<<endl;
}
/* for(int i = 0; i < MAX; i++){
for(int j = 0; j < MAX; j++){
cout<<adj[i][j]<<endl;
}
}*/
}/*End of create_graph()*/
int findpath(int s, int d, int path[MAX], int* sdist)
{
struct node state[MAX];
*sdist =0;
int i, min, count = 0, current, newdist, u, v;
// *sdist = 0;
/* Make all nodes temporary */
//cout<<n<<" This is n"<<endl;
for (i = 1; i <= n; i++)
{
state[i].predecessor = 0;
state[i].dist = INF;
state[i].status = TEMP;
}
/*Source node should be permanent*/
state[s].predecessor = 0;
state[s].dist = 0;
state[s].status = PERM;
/*Starting from source node until destination is found*/
current = s;
while (current != d)
{
for (i = 1; i <= n; i++)
{
/*Checks for adjacent temporary nodes */
if (adj[current][i] > 0 && state[i].status == TEMP)
{
newdist = state[current].dist + adj[current][i];
/*Checks for Relabeling*/
if (newdist < state[i].dist)
{
state[i].predecessor = current;
state[i].dist = newdist;
}
}
}/*End of for*/
/*Search for temporary node with minimum distand make it current node*/
min = INF;
current = 0;
for (i = 1; i <= n; i++)
{
if (state[i].status == TEMP && state[i].dist < min)
{
min = state[i].dist;
current = i;
}
}/*End of for*/
if (current == 0) /*If Source or Sink node is isolated*/
return 0;
state[current].status = PERM;
}/*End of while*/
/* Getting full path in array from destination to source */
while (current != 0)
{
count++;
path[count] = current;
current = state[current].predecessor;
}
/*Getting distance from source to destination*/
for (i = count; i > 1; i--)
{
u = path[i];
v = path[i - 1];
//*sdist += adj[u][v];
*sdist += adj[u][v];
}
return (count);
}/*End of findpath()*/
main()
{
int i, j;
int source, dest;
int path[MAX];
int count;
int minDist;
int distance;
int shortest_path = 0;
create_graph();
/* printf("The adjacency matrix is :\n");
display();
*/
for (auto i : the_list_for_farms) {
//cout<<i<<endl;
minDist = INF;
for (auto l : the_list_for_ports) {
//cout<<l<<endl;
count = findpath(i, l, path, &distance);
if(distance != 0){
if (distance < minDist){
minDist = distance;
}
}
}
shortest_path += minDist;
}
cout << shortest_path << endl;
return 0;
}/*End of main()*/

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:

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:

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:

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:

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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:

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:

input
200000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1652889357

user output
(empty)