Submission #746185

#	Time	Username	Problem	Language	Result	Execution time	Memory
746185		rahulverma	Network (BOI15_net)	Java	100 / 100	1814 ms	158776 KiB

net

import java.io.*;
import java.util.*;

public class net {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		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++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken()) - 1;
			int v2 =Integer.parseInt(st.nextToken()) - 1;
			graph.get(v1).add(v2);
			graph.get(v2).add(v1);
		}
		int root = 0;
		for(int i = 0; i < n; i++) {
			if(graph.get(i).size() != 1) {
				root = i;
			}
		}
		int[] dist = new int[n];
		Queue<Integer> q = new LinkedList<Integer>();
		Arrays.fill(dist, -1);
		q.add(root);
		dist[root] = 0;
		ArrayList<Integer> ans = new ArrayList<Integer>();
		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);
					if(graph.get(node2).size() == 1) {
						ans.add(node2 + 1);
					}
				}
			}
		}

		PrintWriter pw = new PrintWriter(System.out);
		pw.println((ans.size() + 1) / 2);
		for(int i = 0; i < ans.size() / 2; i++) {
			pw.println(ans.get(i) + " " + ans.get(i + ans.size() / 2));
		}
		if(ans.size() % 2 == 1) {
			pw.println(ans.get(ans.size() - 1) + " " + ans.get(0));
		}
		pw.close();
	}

}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37