import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; import java.util.TreeSet; /* * * the most obvious solution: bipartite matching (with hopcroft-karp) * */ /* Uses the following greedy strategy: * -take first the node with the minimal number of edges pair it with the neighbor with the minimal number of edges. * -remove both nodes, update the graph * * if an equation has no neighbors and is not paired -> impossible * * Running time O(N log(N)) * */ public class EgorGreedy { private static class Node implements Comparable{ int pos; int value; public Node(int pos, int value){ this.pos=pos; this.value=value; } @Override public int compareTo(Node arg0) { if(value[] graph=new TreeSet[gSize]; for(int i=0;i(); Map res2id=new HashMap(); long[][] equations=new long[N][]; for(int i=0;i queue=new PriorityQueue(); for(int i=0;i=N) continue; else{ System.out.println("impossible"); return; } } //find greedy the best int min=Integer.MAX_VALUE; int bestIndex=-1; //System.out.println("candidates "+graph[current.pos]); for(int candidate:graph[current.pos]){ if(cnts[candidate]=0) queue.offer(new Node(neighbour, cnts[rem])); } } } for(String s:output) System.out.println(s); } }