Submission #736655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
736655	2023-05-06T04:44:15 Z	rahulverma	Network (BOI15_net)	Java 11	0 / 100	158 ms	11968 KB

net

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>();
		for(int i = 0; i < n; i++) {
			if(graph.get(i).size() == 1) {
				ans.add(i+1);
				if(i == 0) found = true;
			}
		}
		if(found) ans.add(1);
		Collections.sort(ans, (a, b) -> (int) (System.currentTimeMillis()%2)*-1 + 1);
		System.out.println((int) ans.size()/2);
		for(int i = 0; i < ans.size()/2; i += 1) {
			System.out.println(ans.get(2*i) + " " + ans.get(2*i + 1));
		}
	}

}

Subtask #1

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	11968 KB	Output is correct
2	Correct	147 ms	11656 KB	Output is correct
3	Correct	148 ms	11380 KB	Output is correct
4	Correct	143 ms	11484 KB	Output is correct
5	Correct	158 ms	11244 KB	Output is correct
6	Correct	140 ms	11528 KB	Output is correct
7	Correct	142 ms	11420 KB	Output is correct
8	Correct	156 ms	11584 KB	Output is correct
9	Correct	142 ms	11464 KB	Output is correct
10	Incorrect	145 ms	11456 KB	Breaking single line is causing network to disconnect.
11	Halted	0 ms	0 KB	-

Subtask #2

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	11968 KB	Output is correct
2	Correct	147 ms	11656 KB	Output is correct
3	Correct	148 ms	11380 KB	Output is correct
4	Correct	143 ms	11484 KB	Output is correct
5	Correct	158 ms	11244 KB	Output is correct
6	Correct	140 ms	11528 KB	Output is correct
7	Correct	142 ms	11420 KB	Output is correct
8	Correct	156 ms	11584 KB	Output is correct
9	Correct	142 ms	11464 KB	Output is correct
10	Incorrect	145 ms	11456 KB	Breaking single line is causing network to disconnect.
11	Halted	0 ms	0 KB	-

Subtask #3

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	11968 KB	Output is correct
2	Correct	147 ms	11656 KB	Output is correct
3	Correct	148 ms	11380 KB	Output is correct
4	Correct	143 ms	11484 KB	Output is correct
5	Correct	158 ms	11244 KB	Output is correct
6	Correct	140 ms	11528 KB	Output is correct
7	Correct	142 ms	11420 KB	Output is correct
8	Correct	156 ms	11584 KB	Output is correct
9	Correct	142 ms	11464 KB	Output is correct
10	Incorrect	145 ms	11456 KB	Breaking single line is causing network to disconnect.
11	Halted	0 ms	0 KB	-