Task: | Sadonkorjuu |
Sender: | EmuBird |
Submission time: | 2022-11-13 17:00:39 +0200 |
Language: | Java |
Status: | READY |
Result: | 33 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 33 |
#2 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.13 s | 1, 2 | details |
#2 | ACCEPTED | 0.12 s | 1, 2 | details |
#3 | ACCEPTED | 0.12 s | 1, 2 | details |
#4 | ACCEPTED | 0.13 s | 1, 2 | details |
#5 | ACCEPTED | 0.13 s | 1, 2 | details |
#6 | ACCEPTED | 0.21 s | 1, 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | ACCEPTED | 0.21 s | 1, 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | ACCEPTED | 0.20 s | 1, 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 2 | details |
#12 | TIME LIMIT EXCEEDED | -- | 2 | details |
#13 | TIME LIMIT EXCEEDED | -- | 2 | details |
#14 | TIME LIMIT EXCEEDED | -- | 2 | details |
#15 | ACCEPTED | 0.23 s | 1, 2 | details |
#16 | ACCEPTED | 0.20 s | 1, 2 | details |
#17 | ACCEPTED | 0.20 s | 1, 2 | details |
#18 | ACCEPTED | 0.21 s | 1, 2 | details |
#19 | ACCEPTED | 0.21 s | 1, 2 | details |
#20 | ACCEPTED | 0.21 s | 1, 2 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2 | details |
#22 | TIME LIMIT EXCEEDED | -- | 2 | details |
#23 | TIME LIMIT EXCEEDED | -- | 2 | details |
#24 | ACCEPTED | 0.21 s | 1, 2 | details |
#25 | TIME LIMIT EXCEEDED | -- | 2 | details |
#26 | ACCEPTED | 0.20 s | 1, 2 | details |
#27 | TIME LIMIT EXCEEDED | -- | 2 | details |
#28 | ACCEPTED | 0.21 s | 1, 2 | details |
#29 | TIME LIMIT EXCEEDED | -- | 2 | details |
#30 | ACCEPTED | 0.21 s | 1, 2 | details |
#31 | TIME LIMIT EXCEEDED | -- | 2 | details |
Code
import java.util.ArrayList;import java.util.LinkedList;import java.util.Scanner;public class Cities2 {public static void main(String[] args) {Scanner input = new Scanner(System.in);int cityCount = Integer.parseInt(input.nextLine());City[] cities = new City[cityCount];ArrayList<Route> cursors = new ArrayList<>();// Citiesint i = 0;for (String s : input.nextLine().split(" ")) {boolean isField = s.equals("1");City city = new City(isField);cities[i++] = city;}// Routesfor (int linei = 1; linei < cityCount; linei++) {String[] line = input.nextLine().split(" ");City cityA = cities[Integer.parseInt(line[0]) - 1];City cityB = cities[Integer.parseInt(line[1]) - 1];int length = Integer.parseInt(line[2]);Route route1 = new Route(cityA, cityB, length);if (!cityA.isField) cursors.add(route1);else cityA.routes.add(route1);Route route2 = new Route(cityB, cityA, length);if (!cityB.isField) cursors.add(route2);else cityB.routes.add(route2);}// Actual stuff starts here.long totalLength = 0;while (!cursors.isEmpty()) {ArrayList<Route> nextCursors = new ArrayList<>();for (Route route : cursors) {City destination = route.to;destination.routes.remove(route);int newLength = route.from.shortestRoute + route.length;if (newLength < destination.shortestRoute) {totalLength = totalLength - (destination.shortestRoute == Integer.MAX_VALUE ? 0 : destination.shortestRoute) + newLength;destination.shortestRoute = newLength;nextCursors.addAll(destination.routes);}}cursors = nextCursors;}System.out.println(totalLength);}public static class City {public boolean isField;public LinkedList<Route> routes = new LinkedList<>();public int shortestRoute = Integer.MAX_VALUE;public City(boolean isField) {this.isField = isField;if (!isField) shortestRoute = 0;}}public static class Route {public City from;public City to;public int length;public Route(City from, City to, int length) {this.from = from;this.to = to;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: 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: 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: TIME LIMIT EXCEEDED
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: ACCEPTED
input |
---|
1000 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 ... |
correct output |
---|
293576 |
user output |
---|
293576 |
Test 9
Group: 2
Verdict: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1543963 |
user output |
---|
1543963 |
Test 19
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
39606 |
user output |
---|
39606 |
Test 20
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 ... |
correct output |
---|
321598 |
user output |
---|
321598 |
Test 21
Group: 2
Verdict: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
291990 |
user output |
---|
291990 |
Test 25
Group: 2
Verdict: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
200000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1652889357 |
user output |
---|
(empty) |