oj.uz

답안 #739645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739645 2023-05-10T21:47:56 Z rahulverma Network (BOI15_net) Java 11
0 / 100
 143 ms 11576 KB 
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());
		}
	}
 
}

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 143 ms 11576 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 143 ms 11576 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 143 ms 11576 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -