CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:lompakkomies
Submission time:2022-11-04 10:38:20 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.13 s1, 2details
#2ACCEPTED0.13 s1, 2details
#3ACCEPTED0.13 s1, 2details
#40.13 s1, 2details
#5ACCEPTED0.13 s1, 2details
#60.23 s1, 2details
#7--2details
#80.24 s1, 2details
#9--2details
#100.22 s1, 2details
#11--2details
#12--2details
#13--2details
#14--2details
#150.88 s1, 2details
#160.23 s1, 2details
#170.24 s1, 2details
#180.23 s1, 2details
#190.23 s1, 2details
#200.22 s1, 2details
#21--2details
#22--2details
#23--2details
#240.23 s1, 2details
#25--2details
#26ACCEPTED0.23 s1, 2details
#27--2details
#280.21 s1, 2details
#29--2details
#300.24 s1, 2details
#31--2details

Code

import java.util.Scanner;
public class Sadonkorjuu {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] cities = new int[n];
for(int i = 0; i < n; i++) {
cities[i] = scan.nextInt();
}
int[][] connections = new int[2*(n-1)][3];
for(int i = 0; i < n-1; i++) {
connections[i][0] = scan.nextInt();
connections[i][1] = scan.nextInt();
connections[i][2] = scan.nextInt();
connections[i+n-1][1] = connections[i][0];
connections[i+n-1][0] = connections[i][1];
connections[i+n-1][2] = connections[i][2];
}
int temp1 = 0, temp2 = 0, temp3 = 0;
quickSort(connections, 0, n - 1);
int[] cityLocations = new int[n+1];
temp1 = 1;
for(int i = 0; i < connections.length; i++) {
if(temp1 == connections[i][0]) {
cityLocations[temp1 - 1] = i;
temp1++;
}
}
cityLocations[n] = connections.length;
int[] distances = new int[n];
for(int i = 0; i < n; i++) {
distances[i] = -1;
}
int sum = 0;
for(int i = 0; i < n; i++) {
if(cities[i] == 1) {
distance(connections, cityLocations, cities, distances, i, 0, -1, i);
if(distances[i] != -1) {
sum += distances[i];
}
}
}
System.out.println(sum);
}
public static void distance(int[][] connections, int[] cityLocations, int[] cities, int[] distances, int cityNum, int distance, int prevCity, int startCity) {
if(cities[cityNum] == 1) {
for(int i = cityLocations[cityNum]; i < cityLocations[cityNum + 1]; i++) {
if(connections[i][1]-1 != prevCity) {
if(distance + connections[i][2]< distances[startCity] || distances[startCity] == -1) {
distance(connections, cityLocations, cities, distances, connections[i][1]-1, distance + connections[i][2], cityNum, startCity);
}
}
}
return;
} else {
if(distance < distances[startCity] || distances[startCity] == -1) {
distances[startCity] = distance;
return;
}
}
return;
}
static void swap(int[][] connections, int i, int j)
{
int temp1 = connections[i][0];
int temp2 = connections[i][1];
int temp3 = connections[i][2];
connections[i][0] = connections[j][0];
connections[i][1] = connections[j][1];
connections[i][2] = connections[j][2];
connections[j][0] = temp1;
connections[j][1] = temp2;
connections[j][2] = temp3;
}
static int partition(int[][] connections, int low, int high)
{
// pivot
int pivot = connections[high][0];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (connections[j][0] < pivot) {
i++;
swap(connections, i, j);
}
}
swap(connections, i + 1, high);
return (i + 1);
}
static void quickSort(int[][] connections, int low, int high)
{
if (low < high) {
int pi = partition(connections, low, high);
quickSort(connections, low, pi - 1);
quickSort(connections, pi + 1, high);
}
}
}

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:

input
5
0 1 1 1 0
1 2 10
2 3 20
3 4 30
...

correct output
80

user output
100

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
519

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
480688

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
4051

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:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
126238345

user output
127416719

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
462945

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
53606

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
227620

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
44378

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
242998

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
293431

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: 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:

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:

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
7987

user output
42

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:

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
4657693

user output
23846

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)