Task: | Distance Code |
Sender: | William Bille Meyling |
Submission time: | 2019-03-06 19:22:49 +0200 |
Language: | Java |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | RUNTIME ERROR | 0 |
#2 | RUNTIME ERROR | 0 |
#3 | RUNTIME ERROR | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.26 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.25 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.26 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.25 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.26 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.26 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.26 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.24 s | 1, 2, 3 | details |
#9 | RUNTIME ERROR | 0.21 s | 1, 2, 3 | details |
#10 | WRONG ANSWER | 0.25 s | 1, 2, 3 | details |
#11 | RUNTIME ERROR | 0.20 s | 1, 2, 3 | details |
#12 | ACCEPTED | 0.30 s | 2, 3 | details |
#13 | RUNTIME ERROR | 0.21 s | 2, 3 | details |
#14 | RUNTIME ERROR | 0.21 s | 2, 3 | details |
#15 | RUNTIME ERROR | 0.21 s | 2, 3 | details |
#16 | TIME LIMIT EXCEEDED | -- | 3 | details |
#17 | TIME LIMIT EXCEEDED | -- | 3 | details |
#18 | TIME LIMIT EXCEEDED | -- | 3 | details |
#19 | TIME LIMIT EXCEEDED | -- | 3 | details |
#20 | ACCEPTED | 0.25 s | 1, 2, 3 | details |
Code
//thinking depth first with iterative deepening maybe (though slow)//using heapimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Comparator;import java.util.HashSet;import java.util.PriorityQueue;public class Distance_Code_v3 {private static class Node implements Comparable<Node>{int number;HashSet<Node> nbs = new HashSet<>();public Node(int number){this.number = number;}@Overridepublic int compareTo(Node o) {return Integer.compare(this.nbs.size(), o.nbs.size());}}private static class Node2{int number;ArrayList<Node2> children = new ArrayList<>();public Node2(int number){this.number = number;}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int type = Integer.valueOf(br.readLine());int N = Integer.valueOf(br.readLine());if(type == 1){ArrayList<Node> nodes = new ArrayList<>();for(int i = 0; i < N; i++) nodes.add(null);for(int i = 0; i < N - 1; i++){String[] input = br.readLine().split(" ");int a = Integer.valueOf(input[0])-1;int b = Integer.valueOf(input[1])-1;if(nodes.get(a) == null){nodes.set(a, new Node(a));}if(nodes.get(b) == null) {nodes.set(b, new Node(b));}nodes.get(a).nbs.add(nodes.get(b));nodes.get(b).nbs.add(nodes.get(a));}nodes.sort(new Comparator<Node>() {@Overridepublic int compare(Node o1, Node o2) {return Integer.compare(o1.nbs.size(), o2.nbs.size());}});PriorityQueue<Node> heap = new PriorityQueue<>(nodes);ArrayList<Integer> result = new ArrayList<>();while(!heap.isEmpty()){Node curr = heap.poll();result.add(curr.number);for(Node n: curr.nbs){n.nbs.remove(curr);heap.remove(n);heap.add(n);}}for(int i = 0; i < result.size(); i++){System.out.print((result.get(i)+1) + " ");}}else{inputs = br.readLine().split(" ");//if distance == 2 -> same depth && same parent//if distance == 1 -> its the parent//if distance == 3 -> different depth "different parent"//if distance == 4 -> same depth different parent//no its wronginputIndex = inputs.length-1;Node2 root = new Node2(nextNumber);ArrayList<Node2> temp = new ArrayList<>();temp.add(root);decodeAsBFS(temp, 1);dfs(root);}}private static int nextNumber = 1;private static int inputIndex;private static String[] inputs;private static void decodeAsBFS(ArrayList<Node2> siblings, int depth){int siblingIndex = 0;while(inputIndex > -1){int diff = Integer.valueOf(inputs[inputIndex]);inputIndex--;if((diff == 1 && siblings.get(siblingIndex).children.size() == 0 && siblingIndex == 0) || diff == 2){nextNumber++;Node2 child = new Node2(nextNumber);siblings.get(siblingIndex).children.add(child);}else if(diff % 2 == 0){ //assuming a depth shift is never on the current sibling. Turns out this assumptions is false.siblingIndex++;nextNumber++;Node2 child = new Node2(nextNumber);siblings.get(siblingIndex).children.add(child);}else{inputIndex++;inputs[inputIndex] = "1";break;}}for(int i = 0; i < siblings.size(); i++){if(siblings.get(i).children.size() != 0){decodeAsBFS(siblings.get(i).children, depth + 1);}}}private static void dfs(Node2 node){for(int i = 0; i < node.children.size(); i++){System.out.println(node.number + " " + node.children.get(i).number);dfs(node.children.get(i));}}}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 2 2 1 |
correct output |
---|
(empty) |
user output |
---|
1 2 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 3 3 1 2 1 |
correct output |
---|
(empty) |
user output |
---|
1 2 1 3 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 4 3 2 2 1 4 1 |
correct output |
---|
(empty) |
user output |
---|
1 2 2 4 1 3 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 4 2 3 3 4 1 3 |
correct output |
---|
(empty) |
user output |
---|
1 2 1 3 1 4 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 5 3 5 4 1 1 3 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 2 4 1 3 3 5 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 5 3 2 3 4 5 1 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 2 4 2 5 1 3 |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 5 4 3 1 4 4 2 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 1 3 1 4 1 5 |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 10 9 3 8 9 2 9 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 1 3 1 4 1 5 1 6 ... |
Test 9
Group: 1, 2, 3
Verdict: RUNTIME ERROR
input |
---|
1 10 9 2 5 8 7 1 ... |
correct output |
---|
(empty) |
user output |
---|
(empty) |
Error:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 1 out-of-bounds for...
Test 10
Group: 1, 2, 3
Verdict: WRONG ANSWER
input |
---|
1 10 10 4 9 1 4 7 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 2 4 4 6 6 7 7 8 ... |
Test 11
Group: 1, 2, 3
Verdict: RUNTIME ERROR
input |
---|
1 10 2 6 4 3 3 5 ... |
correct output |
---|
(empty) |
user output |
---|
(empty) |
Error:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 1 out-of-bounds for...
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
1 500 10 6 6 255 6 428 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 1 3 1 4 1 5 1 6 ... Truncated |
Test 13
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
1 500 152 466 451 313 158 479 ... |
correct output |
---|
(empty) |
user output |
---|
(empty) |
Error:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 1 out-of-bounds for...
Test 14
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
1 500 109 440 330 190 443 161 ... |
correct output |
---|
(empty) |
user output |
---|
(empty) |
Error:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 1 out-of-bounds for...
Test 15
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
1 500 144 373 257 233 341 318 ... |
correct output |
---|
(empty) |
user output |
---|
(empty) |
Error:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 1 out-of-bounds for...
Test 16
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
1 100000 54983 75172 93807 75172 44082 75172 ... |
correct output |
---|
(empty) |
user output |
---|
(empty) |
Test 17
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
1 100000 88863 19059 86423 76688 98536 95984 ... |
correct output |
---|
(empty) |
user output |
---|
(empty) |
Test 18
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
1 100000 59979 6389 19097 24999 27846 82330 ... |
correct output |
---|
(empty) |
user output |
---|
(empty) |
Test 19
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
1 100000 58761 66001 25102 51081 98625 67861 ... |
correct output |
---|
(empty) |
user output |
---|
(empty) |
Test 20
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 6 2 1 3 2 4 2 ... |
correct output |
---|
(empty) |
user output |
---|
1 2 2 5 2 6 1 3 1 4 |