ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1022. Genealogical Tree

Using priority queue - getting WA#4. Why?
Posted by Stefan Dimov 20 Oct 2014 10:02
I am using priority queue. Priority is determined by the number of elements. The top element is one without parents. When it's removed from the queue, it's being deleted as a parent from all the other elements. I get WA#4. Any idea why?
Re: Using priority queue - getting WA#4. Why?
Posted by Stefan Dimov 21 Oct 2014 11:00
This is my code. Can someone tell me why do I get WA#4?

import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class MartianCouncil {

public static void main(String[] args) {
Hashtable<Integer, TreeNode> global = new Hashtable<Integer, TreeNode>();
Scanner s = new Scanner(System.in);
int n = s.nextInt();
if (n == 0) {
s.close();
return;
}
s.nextLine();
for (int i = 1; i <= n; i++) {
TreeNode node = global.get(i);
if (node == null) {
node = new TreeNode(i);
global.put(i, node);
}
String line = s.nextLine();
String[] nums = line.split(" ");
for (int j = 0; j < nums.length - 1; j++) {
int num = Integer.parseInt(nums[j]);
TreeNode nd = global.get(num);
if (nd == null) {
nd = new TreeNode(num);
global.put(num, nd);
}
}
}
s.close();
print(global);
}

public static void print(Hashtable<Integer, TreeNode> global) {
PriorityQueue<TreeNode> q = new PriorityQueue<TreeNode>();
StringBuilder res = new StringBuilder("");
while (!q.isEmpty()) {
TreeNode nd = q.poll();
res = res.append((res.length() == 0) ? "" : " ");
res = res.append(nd.getNum());
}
System.out.print(res);
}

public static class TreeNode implements Comparable<MartianCouncil.TreeNode> {

private int num = 0;
private Collection<MartianCouncil.TreeNode> children = new HashSet<MartianCouncil.TreeNode>();
private Collection<MartianCouncil.TreeNode> parents = new HashSet<MartianCouncil.TreeNode>();

public TreeNode(int num) {
this.num = num;
}

public int hashCode() {
return num;
}

public boolean equals(Object o) {
if (o == null) {
return false;
} else if (!(o instanceof MartianCouncil.TreeNode)) {
return false;
} else {
return (this.hashCode() == o.hashCode());
}
}

}

public boolean removeChild(MartianCouncil.TreeNode child) {
child.parents.remove(this);
return children.remove(child);
}

}

public boolean removeParent(TreeNode parent) {
parent.children.remove(this);
return parents.remove(parent);
}

public void removeAllChildren() {
Iterator<TreeNode> it = children.iterator();
while (it.hasNext()) {
TreeNode child = it.next();
child.parents.remove(this);
}
children.clear();
}

public int getNum() {
return num;
}

public Collection<TreeNode> getChildren() {
return children;
}

public int getParentsNum() {
return parents.size();
}

@Override
public int compareTo(MartianCouncil.TreeNode nd) {
return Math.round(Math.signum(this.getParentsNum() - nd.getParentsNum()));
}

}

public class TreeNodeComp implements Comparator<MartianCouncil.TreeNode> {

@Override
public int compare(MartianCouncil.TreeNode nd1, MartianCouncil.TreeNode nd2) {
return Math.round(Math.signum(nd1.getParentsNum() - nd2.getParentsNum()));
}

}

}