CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:lompakkomies
Submission time:2022-11-04 10:30:59 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.13 s1, 2details
#2ACCEPTED0.13 s1, 2details
#30.24 s1, 2details
#40.22 s1, 2details
#50.23 s1, 2details
#6--1, 2details
#7--2details
#80.46 s1, 2details
#9--2details
#100.38 s1, 2details
#11--2details
#12--2details
#13--2details
#14--2details
#15--1, 2details
#160.44 s1, 2details
#170.40 s1, 2details
#180.61 s1, 2details
#190.42 s1, 2details
#200.46 s1, 2details
#21--2details
#22--2details
#23--2details
#240.48 s1, 2details
#25--2details
#260.47 s1, 2details
#27--2details
#28--1, 2details
#29--2details
#30--1, 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();
        }

        //System.out.println("ok");

        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];

            //System.out.println("ok");
        }
        int temp1 = 0, temp2 = 0, temp3 = 0;

        for(int i = 0; i < connections.length; i++) {
            for(int j = 0; j < connections.length - 1; j++) {
                if(connections[j][0] > connections[j+1][0]) {
                    temp1 = connections[j][0];
                    temp2 = connections[j][1];
                    temp3 = connections[j][2];

                    connections[j][0] = connections[j+1][0];
                    connections[j][1] = connections[j+1][1];
                    connections[j][2] = connections[j+1][2];

                    connections[j+1][0] = temp1;
                    connections[j+1][1] = temp2;
                    connections[j+1][2] = temp3;
                }
            }
        }

        /*for(int i = 0; i < connections.length; i++) {
            System.out.print(connections[i][0]);
        }*/

        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;

        /*System.out.println("length: " + cityLocations.length);

        for(int k = 0; k < n; k++) {
            //System.out.println("city" + k + "connections:");
            //System.out.println(cityLocations[k] + " " + cityLocations[k+1] + ", ");
            for(int i = cityLocations[k]; i < cityLocations[k+1]; i++) {
                for(int j = 0; j < connections[0].length; j++) {
                    System.out.print(connections[i][j] + ", ");
                }
                System.out.print("\n");
            }
        }

        for(int i = 0; i < cityLocations.length; i++) {
            System.out.print(cityLocations[i] + ", ");
        }*/

        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(distances[i]);
                System.out.println("\n" + i);
                //sum += scan.nextInt();
            }
        }
        System.out.println(sum);

        /*for(int i = 0; i < n; i++) {
            System.out.print(", " + distances[i]);
        }*/
    }

    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) {
                    distance += connections[i][2];
                    if(distance < distances[startCity] || distances[startCity] == -1) {
                        System.out.println( connections[i][0] + ", " +  connections[i][1] + ", " + connections[i][2]);
                        distance(connections, cityLocations, cities, distances, connections[i][1]-1, distance, cityNum, startCity);
                    }
                    distance -= connections[i][2];
                }
            }
            return;
        } else {
            if(distance < distances[startCity] || distances[startCity] == -1) {
                distances[startCity] = distance;
                return;
            }
        }
        return;
    }
}

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:

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

correct output
60

user output
1, 2, 10

0
3, 2, 20

...

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
2, 3, 20
3, 4, 30
4, 5, 40
2, 1, 10

...
Truncated

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
2, 3, 5
2, 1, 1

1
4, 3, 3
...

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
3, 1, 916
3, 5, 694
5, 15, 196
5, 44, 149
3, 37, 386
...
Truncated

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
91, 46, 871
91, 148, 183

90
153, 21, 347
...
Truncated

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

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
4, 5, 688

3
6, 7, 845
7, 8, 830
...
Truncated

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
1, 2, 444

0
5, 6, 635

...
Truncated

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
1, 2, 824
2, 4, 834
4, 8, 34
8, 16, 646
16, 32, 364
...
Truncated

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
22, 44, 497

21
28, 56, 935
56, 112, 842
...
Truncated

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
1, 2, 370
1, 3, 19
3, 6, 41

0
...
Truncated

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
1, 2, 646
2, 4, 733
4, 8, 766
8, 16, 320
16, 32, 416
...
Truncated

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
1, 2, 1
2, 4, 1
4, 8, 1
8, 16, 1
16, 32, 1
...
Truncated

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

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

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)