Submission #739645

#TimeUsernameProblemLanguageResultExecution timeMemory
739645rahulvermaNetwork (BOI15_net)Java
0 / 100
143 ms11576 KiB
import java.io.*; import java.util.*; public class net { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); for(int i = 0; i < n; i++) graph.add(new ArrayList<Integer>()); for(int i = 1; i < n; i++) { int v1 = s.nextInt() - 1; int v2 = s.nextInt() - 1; graph.get(v1).add(v2); graph.get(v2).add(v1); } int[] dist = new int[n]; Queue<Integer> q = new LinkedList<Integer>(); Arrays.fill(dist, -1); q.add(0); dist[0] = 0; while(!q.isEmpty()) { int node = q.poll(); for(int node2: graph.get(node)) { if(dist[node2] == -1) { dist[node2] = dist[node] + 1; q.add(node2); } } } /*for(int i = 0; i < n; i++) { System.out.println(dist[i]); }*/ boolean found = true; ArrayList<Integer> ans = new ArrayList<Integer>(); ans.add(1); for(int i = 1; i < n; i++) { if(graph.get(i).size() == 1) { ans.add(i+1); } } Queue<Integer> stack = new LinkedList<Integer>(); Collections.sort(ans, (a, b) -> -1*(dist[a-1] - dist[b-1])); System.out.println((int) ans.size()/2); for(int i = 0; i < ans.size(); i++) { stack.add(ans.get(i)); } //System.out.println(ans); while(!stack.isEmpty()) { int cur = stack.poll(); //System.out.println(stack); while(dist[cur-1] == dist[stack.peek()-1]) { int ele = stack.poll(); stack.add(ele); //System.out.println(stack); } System.out.println(cur + " " + stack.poll()); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...