CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Septicuss
Submission time:2022-11-01 18:44:52 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.07 s1, 2details
#2ACCEPTED0.07 s1, 2details
#3ACCEPTED0.07 s1, 2details
#4ACCEPTED0.07 s1, 2details
#50.07 s1, 2details
#6ACCEPTED0.13 s1, 2details
#7--2details
#80.58 s1, 2details
#9--2details
#100.50 s1, 2details
#11--2details
#12--2details
#13--2details
#14--2details
#15ACCEPTED0.13 s1, 2details
#160.60 s1, 2details
#170.57 s1, 2details
#180.28 s1, 2details
#190.55 s1, 2details
#200.59 s1, 2details
#21--2details
#22--2details
#23--2details
#24ACCEPTED0.67 s1, 2details
#25--2details
#26ACCEPTED0.65 s1, 2details
#27--2details
#28ACCEPTED0.13 s1, 2details
#29--2details
#30ACCEPTED0.14 s1, 2details
#31--2details

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class E430 {

	static int n;
	static ArrayList<WeightedNode> ports = new ArrayList<>();
	static ArrayList<Integer> portsInt = new ArrayList<>();

	static HashMap<Integer, Integer> mins = new HashMap<>();

	public static void main(String[] args) {
		FastReader reader = new FastReader();
		PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

		n = reader.nextInt();

		ArrayList<WeightedNode> nodes = new ArrayList<>();

		int a, b, c, t;
		// City types
		for (int id = 1; id < (n + 1); id++) {
			t = reader.nextInt();
			WeightedNode node = new WeightedNode(id, t, id - 1);
			if (t == 0) {
				ports.add(node);
				portsInt.add(id - 1);
			}
			nodes.add(node);
		}

		WeightedGraph graph = new WeightedGraph(nodes);

		// Connections
		for (int i = 0; i < (n - 1); i++) {
			a = reader.nextInt() - 1;
			b = reader.nextInt() - 1;
			c = reader.nextInt();
			graph.addWeightedEdge(a, b, c);
		}

		for (WeightedNode port : ports)
			graph.dijkstra(port);

		long sum = 0;

		for (int value : mins.values()) {
			sum += value;
		}

		writer.println(sum);
		writer.flush();
		writer.close();
	}

	// ------------------------------------------------------

	static class WeightedGraph {
		ArrayList<WeightedNode> nodes = new ArrayList<WeightedNode>();

		public WeightedGraph(ArrayList<WeightedNode> nodes) {
			this.nodes = nodes;
		}

		void dijkstra(WeightedNode node) {
			PriorityQueue<WeightedNode> queue = new PriorityQueue<>();
			node.distance = 0;

			queue.addAll(nodes);

			while (!queue.isEmpty()) {
				WeightedNode current = queue.remove();

				for (WeightedNode neighbor : current.neighbors) {
					if (neighbor.type == 0)
						continue;
					if (queue.contains(neighbor)) {
						if (neighbor.distance > current.distance + current.weightMap.get(neighbor)) {
							neighbor.distance = (current.distance + current.weightMap.get(neighbor));

							if (mins.containsKey(neighbor.id)) {
								mins.put(neighbor.id, Math.min(mins.get(neighbor.id), neighbor.distance));
							} else {
								mins.put(neighbor.id, neighbor.distance);
							}

							neighbor.parent = current;
							queue.remove(neighbor);
							queue.add(neighbor);
						}
					}
				}

			}

		}

		void addWeightedEdge(int a, int b, int c) {
			WeightedNode first = nodes.get(a);
			WeightedNode second = nodes.get(b);
			first.neighbors.add(second);
			first.weightMap.put(second, c);
			second.neighbors.add(first);
			second.weightMap.put(first, c);
		}
	}

	static class WeightedNode implements Comparable<WeightedNode> {
		int id;
		int type;
		ArrayList<WeightedNode> neighbors = new ArrayList<>();
		HashMap<WeightedNode, Integer> weightMap = new HashMap<>();
		boolean visited = false;
		WeightedNode parent;
		int distance;
		int index;

		public WeightedNode(int id, int type, int index) {
			this.id = id;
			this.type = type;
			distance = Integer.MAX_VALUE;
			this.index = index;
		}

		@Override
		public String toString() {
			return String.valueOf(id);
		}

		@Override
		public int compareTo(WeightedNode o) {
			return this.distance - o.distance;
		}

	}

	static class FastReader {

		private BufferedReader br;
		private StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
			st = null;
			br = null;
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		String nextLine() {
			String str = "";

			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}

			return str;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		BigInteger nextBigInteger() {
			return new BigInteger(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

	}

}

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:

input
5
0 1 0 1 1
1 2 1
2 3 5
3 4 3
...

correct output
6

user output
-2147483643

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:

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

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

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:

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

correct output
278678

user output
-1065151702336

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

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

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

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

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

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