CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:EmuBird
Submission time:2022-11-12 17:22:08 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.12 s1, 2details
#2ACCEPTED0.15 s1, 2details
#3ACCEPTED0.12 s1, 2details
#40.13 s1, 2details
#5ACCEPTED0.12 s1, 2details
#60.20 s1, 2details
#7--2details
#80.21 s1, 2details
#9--2details
#10ACCEPTED0.20 s1, 2details
#11--2details
#12--2details
#13--2details
#14--2details
#15ACCEPTED0.20 s1, 2details
#16ACCEPTED0.20 s1, 2details
#17ACCEPTED0.20 s1, 2details
#180.20 s1, 2details
#190.20 s1, 2details
#200.20 s1, 2details
#21--2details
#22--2details
#23--2details
#240.20 s1, 2details
#25--2details
#260.20 s1, 2details
#27--2details
#28ACCEPTED0.20 s1, 2details
#29--2details
#30ACCEPTED0.20 s1, 2details
#31--2details

Code

import java.util.ArrayList;
import java.util.Scanner;

public class Cities {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int cityCount = Integer.parseInt(input.nextLine());
        City[] cities = new City[cityCount];
        ArrayList<City> cursors = new ArrayList<>();

        // Cities
        int i = 0;
        for (String s : input.nextLine().split(" ")) {
            boolean isField = s.equals("1");
            City city = new City(isField);
            cities[i++] = city;
            if (!isField) cursors.add(city);
        }

        // Routes
        for (int linei = 1; linei < cityCount; linei++) {
            String[] line = input.nextLine().split(" ");

            City from = cities[Integer.parseInt(line[0]) - 1];
            City to = cities[Integer.parseInt(line[1]) - 1];
            int length = Integer.parseInt(line[2]);

            from.routes.add(new Route(to, length));
            to.routes.add(new Route(from, length));
        }

        // Actual stuff starts here.
        long totalLength = 0;
        while (!cursors.isEmpty()) {
            ArrayList<City> nextCursors = new ArrayList<>();
            for (City city : cursors) {
                for (Route route : city.routes) {
                    int newLength = city.shortestRoute + route.length;
                    if (newLength < route.destination.shortestRoute) {
                        totalLength = totalLength - (route.destination.shortestRoute == Integer.MAX_VALUE ? 0 : route.destination.shortestRoute) + newLength;
                        route.destination.shortestRoute = newLength;
                        if (city.routes.size() > 1) nextCursors.add(route.destination);
                    }
                }
            }
            cursors = nextCursors;
        }

        System.out.println(totalLength);
    }

    public static class City {
        public ArrayList<Route> routes = new ArrayList<>();
        public int shortestRoute = Integer.MAX_VALUE;

        public City(boolean isField) {
            if (!isField) shortestRoute = 0;
        }
    }

    public static class Route {
        public City destination;
        public int length;

        public Route(City destination, int length) {
            this.destination = destination;
            this.length = length;
        }
    }
}

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
50

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
280957

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

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

correct output
3089

user output
3089

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

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

correct output
278678

user output
278678

Test 17

Group: 1, 2

Verdict: ACCEPTED

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

correct output
34929

user output
34929

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
1670260

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
38528

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
301322

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
75682

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
250

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)