CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Finnduino
Submission time:2022-11-07 21:31:34 +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
#50.13 s1, 2details
#60.33 s1, 2details
#7--2details
#80.24 s1, 2details
#9--2details
#100.24 s1, 2details
#11--2details
#12--2details
#13--2details
#14--2details
#15ACCEPTED0.24 s1, 2details
#16ACCEPTED0.26 s1, 2details
#17ACCEPTED0.26 s1, 2details
#180.30 s1, 2details
#190.29 s1, 2details
#200.28 s1, 2details
#21--2details
#22--2details
#23--2details
#240.23 s1, 2details
#25--2details
#260.23 s1, 2details
#27--2details
#280.23 s1, 2details
#29--2details
#300.23 s1, 2details
#31--2details

Code

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class App {
public static void main(String[] args) throws Exception {
//Declaring City count
Scanner scanner = new Scanner(System.in);
int NodeCount = Integer.parseInt(scanner.nextLine());
//Declaring city states
int[] NodeStates;
NodeStates = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
HashMap<Integer, int[][]> RoadDict = new HashMap<Integer, int[][]>();
int[] Ports = new int[0];
//Iterate and build road index:
for (int i = 0; i < NodeCount-1; i++) {
int[] tempArray = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//case 1:
int[][] tempone;
int[][] finalone = {{0, 0}};
if(RoadDict.containsKey(tempArray[0]-1)){
tempone = RoadDict.get(tempArray[0]-1);
finalone = addArrayMember(tempone, new int[]{0,0});
//finalone = Arrays.copyOf(tempone, tempone.length+1);
finalone[tempone.length][0] = tempArray[1]-1;
finalone[tempone.length][1] = tempArray[2];
}
else{
finalone[0][0] = tempArray[1]-1;
finalone[0][1] = tempArray[2];
}
RoadDict.put(tempArray[0]-1,finalone);
//case 2:
int[][] temptwo;
int[][] finaltwo = {{0, 0}};
if(RoadDict.containsKey(tempArray[1]-1)){
temptwo = RoadDict.get(tempArray[1]-1);
finaltwo = addArrayMember(temptwo, new int[]{0,0});
//finaltwo = Arrays.copyOf(temptwo, temptwo.length+1);
finaltwo[temptwo.length][0] = tempArray[0]-1;
finaltwo[temptwo.length][1] = tempArray[2];
}
else{
finaltwo[0][0] = tempArray[0]-1;
finaltwo[0][1] = tempArray[2];
}
RoadDict.put(tempArray[1]-1,finaltwo);
if(NodeStates[tempArray[0]] == 0){
Ports = addMember(Ports, tempArray[0]);
}
}
scanner.close();
Node[] NodeList = new Node[NodeCount];
for (int i = 0; i < NodeCount; i++) {
NodeList[i] = new Node();
NodeList[i].value = i;
if(NodeStates[i]==0){
NodeList[i].addDistance(0);
}
}
Node[] PortNodes = new Node[Ports.length];
int counter = 0;
for (int i : Ports) {
PortNodes[counter] = NodeList[i];
counter ++;
}
for(Node startingNode : PortNodes){
Node node = startingNode;
int startingNodeValue = startingNode.value;
boolean[] travelledNodes = new boolean[NodeCount];
for(boolean state : travelledNodes){
state = false;
}
ArrayList<Node> Queue = new ArrayList<Node>();
Queue.add(startingNode);
travelledNodes[startingNodeValue] = true;
while(Queue.size()>0){
node = Queue.get(0);
Queue.remove(0);
int nodeValue = node.value;
for(int[] neighbor : RoadDict.get(nodeValue)){
int neighborValue = neighbor[0];
Node neighborNode = NodeList[neighborValue];
if(NodeStates[neighborValue]==0){
travelledNodes[neighborValue] = true;
}
else if(!travelledNodes[neighborValue]){
travelledNodes[neighborValue] = true;
Queue.add(neighborNode);
neighborNode.addDistance(connection(nodeValue, neighborValue, RoadDict)+node.distance);
}
}
}
}
int sum = 0;
for(Node node : NodeList){
sum += node.distance;
}
System.out.println(sum);
}
public static int[][] addArrayMember(int[][] arr, int[] x){
int size = arr.length;
int[][] newArr = new int[size+1][1];
for (int i = 0; i < size; i++) {
newArr[i] = arr[i];
}
newArr[size] = x;
return newArr;
}
public static int[] addMember( int[] arr, int x)
{
int size = arr.length;
int[] newArr = new int[size+1];
for (int i = 0; i < size; i++) {
newArr[i] = arr[i];
}
newArr[size] = x;
return newArr;
}
public static int connection(int node, int target, HashMap<Integer, int[][]> RoadDict){
for (int[] con : RoadDict.get(node)) {
if(con[0] == target){
return con[1];
}
}
return 0;
}
}
class Node{
int value;
int distance = Integer.MAX_VALUE;
void addDistance(int testDistance){
if(testDistance < Node.this.distance){
Node.this.distance = testDistance;
}
}
}

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
200

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
10

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)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1000 out of bou...

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)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1000 out of bou...

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)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1000 out of bou...

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
1822744

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
49885

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
383629

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
2147483147

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
2147483147

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
2147482649

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
2147482649

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)