Task: | Sadonkorjuu |
Sender: | Septicuss |
Submission time: | 2022-11-01 18:44:52 +0200 |
Language: | Java |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.07 s | 1, 2 | details |
#2 | ACCEPTED | 0.07 s | 1, 2 | details |
#3 | ACCEPTED | 0.07 s | 1, 2 | details |
#4 | ACCEPTED | 0.07 s | 1, 2 | details |
#5 | WRONG ANSWER | 0.07 s | 1, 2 | details |
#6 | ACCEPTED | 0.13 s | 1, 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | WRONG ANSWER | 0.58 s | 1, 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | WRONG ANSWER | 0.50 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.13 s | 1, 2 | details |
#16 | WRONG ANSWER | 0.60 s | 1, 2 | details |
#17 | WRONG ANSWER | 0.57 s | 1, 2 | details |
#18 | WRONG ANSWER | 0.28 s | 1, 2 | details |
#19 | WRONG ANSWER | 0.55 s | 1, 2 | details |
#20 | WRONG ANSWER | 0.59 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.67 s | 1, 2 | details |
#25 | TIME LIMIT EXCEEDED | -- | 2 | details |
#26 | ACCEPTED | 0.65 s | 1, 2 | details |
#27 | TIME LIMIT EXCEEDED | -- | 2 | details |
#28 | ACCEPTED | 0.13 s | 1, 2 | details |
#29 | TIME LIMIT EXCEEDED | -- | 2 | details |
#30 | ACCEPTED | 0.14 s | 1, 2 | details |
#31 | TIME LIMIT EXCEEDED | -- | 2 | details |
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: WRONG ANSWER
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: 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: WRONG ANSWER
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: 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: WRONG ANSWER
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: 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: WRONG ANSWER
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: WRONG ANSWER
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: WRONG ANSWER
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: WRONG ANSWER
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: WRONG ANSWER
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: 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) |