| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 746185 |
2023-05-21T18:10:12 Z |
rahulverma |
Network (BOI15_net) |
Java 11 |
|
1814 ms |
158776 KB |
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();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
10376 KB |
Output is correct |
| 2 |
Correct |
110 ms |
10428 KB |
Output is correct |
| 3 |
Correct |
118 ms |
10204 KB |
Output is correct |
| 4 |
Correct |
110 ms |
10308 KB |
Output is correct |
| 5 |
Correct |
113 ms |
10472 KB |
Output is correct |
| 6 |
Correct |
118 ms |
10236 KB |
Output is correct |
| 7 |
Correct |
112 ms |
10364 KB |
Output is correct |
| 8 |
Correct |
110 ms |
10336 KB |
Output is correct |
| 9 |
Correct |
113 ms |
10396 KB |
Output is correct |
| 10 |
Correct |
121 ms |
10484 KB |
Output is correct |
| 11 |
Correct |
122 ms |
10532 KB |
Output is correct |
| 12 |
Correct |
114 ms |
10352 KB |
Output is correct |
| 13 |
Correct |
126 ms |
10276 KB |
Output is correct |
| 14 |
Correct |
116 ms |
10416 KB |
Output is correct |
| 15 |
Correct |
116 ms |
10348 KB |
Output is correct |
| 16 |
Correct |
115 ms |
10352 KB |
Output is correct |
| 17 |
Correct |
117 ms |
10228 KB |
Output is correct |
| 18 |
Correct |
110 ms |
10472 KB |
Output is correct |
| 19 |
Correct |
108 ms |
10428 KB |
Output is correct |
| 20 |
Correct |
106 ms |
10472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
10376 KB |
Output is correct |
| 2 |
Correct |
110 ms |
10428 KB |
Output is correct |
| 3 |
Correct |
118 ms |
10204 KB |
Output is correct |
| 4 |
Correct |
110 ms |
10308 KB |
Output is correct |
| 5 |
Correct |
113 ms |
10472 KB |
Output is correct |
| 6 |
Correct |
118 ms |
10236 KB |
Output is correct |
| 7 |
Correct |
112 ms |
10364 KB |
Output is correct |
| 8 |
Correct |
110 ms |
10336 KB |
Output is correct |
| 9 |
Correct |
113 ms |
10396 KB |
Output is correct |
| 10 |
Correct |
121 ms |
10484 KB |
Output is correct |
| 11 |
Correct |
122 ms |
10532 KB |
Output is correct |
| 12 |
Correct |
114 ms |
10352 KB |
Output is correct |
| 13 |
Correct |
126 ms |
10276 KB |
Output is correct |
| 14 |
Correct |
116 ms |
10416 KB |
Output is correct |
| 15 |
Correct |
116 ms |
10348 KB |
Output is correct |
| 16 |
Correct |
115 ms |
10352 KB |
Output is correct |
| 17 |
Correct |
117 ms |
10228 KB |
Output is correct |
| 18 |
Correct |
110 ms |
10472 KB |
Output is correct |
| 19 |
Correct |
108 ms |
10428 KB |
Output is correct |
| 20 |
Correct |
106 ms |
10472 KB |
Output is correct |
| 21 |
Correct |
115 ms |
10248 KB |
Output is correct |
| 22 |
Correct |
270 ms |
14620 KB |
Output is correct |
| 23 |
Correct |
260 ms |
14592 KB |
Output is correct |
| 24 |
Correct |
246 ms |
14752 KB |
Output is correct |
| 25 |
Correct |
221 ms |
14092 KB |
Output is correct |
| 26 |
Correct |
215 ms |
11976 KB |
Output is correct |
| 27 |
Correct |
258 ms |
14672 KB |
Output is correct |
| 28 |
Correct |
254 ms |
14812 KB |
Output is correct |
| 29 |
Correct |
200 ms |
11900 KB |
Output is correct |
| 30 |
Correct |
127 ms |
10492 KB |
Output is correct |
| 31 |
Correct |
269 ms |
14752 KB |
Output is correct |
| 32 |
Correct |
116 ms |
10372 KB |
Output is correct |
| 33 |
Correct |
120 ms |
10224 KB |
Output is correct |
| 34 |
Correct |
132 ms |
10196 KB |
Output is correct |
| 35 |
Correct |
117 ms |
10444 KB |
Output is correct |
| 36 |
Correct |
125 ms |
10652 KB |
Output is correct |
| 37 |
Correct |
149 ms |
10648 KB |
Output is correct |
| 38 |
Correct |
161 ms |
10836 KB |
Output is correct |
| 39 |
Correct |
116 ms |
10228 KB |
Output is correct |
| 40 |
Correct |
118 ms |
10372 KB |
Output is correct |
| 41 |
Correct |
143 ms |
10268 KB |
Output is correct |
| 42 |
Correct |
131 ms |
10572 KB |
Output is correct |
| 43 |
Correct |
155 ms |
10792 KB |
Output is correct |
| 44 |
Correct |
116 ms |
10508 KB |
Output is correct |
| 45 |
Correct |
128 ms |
10480 KB |
Output is correct |
| 46 |
Correct |
155 ms |
10636 KB |
Output is correct |
| 47 |
Correct |
128 ms |
10548 KB |
Output is correct |
| 48 |
Correct |
127 ms |
10352 KB |
Output is correct |
| 49 |
Correct |
148 ms |
11168 KB |
Output is correct |
| 50 |
Correct |
130 ms |
10372 KB |
Output is correct |
| 51 |
Correct |
123 ms |
10300 KB |
Output is correct |
| 52 |
Correct |
127 ms |
10544 KB |
Output is correct |
| 53 |
Correct |
140 ms |
10776 KB |
Output is correct |
| 54 |
Correct |
123 ms |
10292 KB |
Output is correct |
| 55 |
Correct |
144 ms |
10504 KB |
Output is correct |
| 56 |
Correct |
115 ms |
10436 KB |
Output is correct |
| 57 |
Correct |
133 ms |
10704 KB |
Output is correct |
| 58 |
Correct |
234 ms |
14404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
10376 KB |
Output is correct |
| 2 |
Correct |
110 ms |
10428 KB |
Output is correct |
| 3 |
Correct |
118 ms |
10204 KB |
Output is correct |
| 4 |
Correct |
110 ms |
10308 KB |
Output is correct |
| 5 |
Correct |
113 ms |
10472 KB |
Output is correct |
| 6 |
Correct |
118 ms |
10236 KB |
Output is correct |
| 7 |
Correct |
112 ms |
10364 KB |
Output is correct |
| 8 |
Correct |
110 ms |
10336 KB |
Output is correct |
| 9 |
Correct |
113 ms |
10396 KB |
Output is correct |
| 10 |
Correct |
121 ms |
10484 KB |
Output is correct |
| 11 |
Correct |
122 ms |
10532 KB |
Output is correct |
| 12 |
Correct |
114 ms |
10352 KB |
Output is correct |
| 13 |
Correct |
126 ms |
10276 KB |
Output is correct |
| 14 |
Correct |
116 ms |
10416 KB |
Output is correct |
| 15 |
Correct |
116 ms |
10348 KB |
Output is correct |
| 16 |
Correct |
115 ms |
10352 KB |
Output is correct |
| 17 |
Correct |
117 ms |
10228 KB |
Output is correct |
| 18 |
Correct |
110 ms |
10472 KB |
Output is correct |
| 19 |
Correct |
108 ms |
10428 KB |
Output is correct |
| 20 |
Correct |
106 ms |
10472 KB |
Output is correct |
| 21 |
Correct |
115 ms |
10248 KB |
Output is correct |
| 22 |
Correct |
270 ms |
14620 KB |
Output is correct |
| 23 |
Correct |
260 ms |
14592 KB |
Output is correct |
| 24 |
Correct |
246 ms |
14752 KB |
Output is correct |
| 25 |
Correct |
221 ms |
14092 KB |
Output is correct |
| 26 |
Correct |
215 ms |
11976 KB |
Output is correct |
| 27 |
Correct |
258 ms |
14672 KB |
Output is correct |
| 28 |
Correct |
254 ms |
14812 KB |
Output is correct |
| 29 |
Correct |
200 ms |
11900 KB |
Output is correct |
| 30 |
Correct |
127 ms |
10492 KB |
Output is correct |
| 31 |
Correct |
269 ms |
14752 KB |
Output is correct |
| 32 |
Correct |
116 ms |
10372 KB |
Output is correct |
| 33 |
Correct |
120 ms |
10224 KB |
Output is correct |
| 34 |
Correct |
132 ms |
10196 KB |
Output is correct |
| 35 |
Correct |
117 ms |
10444 KB |
Output is correct |
| 36 |
Correct |
125 ms |
10652 KB |
Output is correct |
| 37 |
Correct |
149 ms |
10648 KB |
Output is correct |
| 38 |
Correct |
161 ms |
10836 KB |
Output is correct |
| 39 |
Correct |
116 ms |
10228 KB |
Output is correct |
| 40 |
Correct |
118 ms |
10372 KB |
Output is correct |
| 41 |
Correct |
143 ms |
10268 KB |
Output is correct |
| 42 |
Correct |
131 ms |
10572 KB |
Output is correct |
| 43 |
Correct |
155 ms |
10792 KB |
Output is correct |
| 44 |
Correct |
116 ms |
10508 KB |
Output is correct |
| 45 |
Correct |
128 ms |
10480 KB |
Output is correct |
| 46 |
Correct |
155 ms |
10636 KB |
Output is correct |
| 47 |
Correct |
128 ms |
10548 KB |
Output is correct |
| 48 |
Correct |
127 ms |
10352 KB |
Output is correct |
| 49 |
Correct |
148 ms |
11168 KB |
Output is correct |
| 50 |
Correct |
130 ms |
10372 KB |
Output is correct |
| 51 |
Correct |
123 ms |
10300 KB |
Output is correct |
| 52 |
Correct |
127 ms |
10544 KB |
Output is correct |
| 53 |
Correct |
140 ms |
10776 KB |
Output is correct |
| 54 |
Correct |
123 ms |
10292 KB |
Output is correct |
| 55 |
Correct |
144 ms |
10504 KB |
Output is correct |
| 56 |
Correct |
115 ms |
10436 KB |
Output is correct |
| 57 |
Correct |
133 ms |
10704 KB |
Output is correct |
| 58 |
Correct |
234 ms |
14404 KB |
Output is correct |
| 59 |
Correct |
1736 ms |
118804 KB |
Output is correct |
| 60 |
Correct |
1783 ms |
119776 KB |
Output is correct |
| 61 |
Correct |
111 ms |
10416 KB |
Output is correct |
| 62 |
Correct |
117 ms |
10288 KB |
Output is correct |
| 63 |
Correct |
1474 ms |
112388 KB |
Output is correct |
| 64 |
Correct |
304 ms |
14872 KB |
Output is correct |
| 65 |
Correct |
447 ms |
18852 KB |
Output is correct |
| 66 |
Correct |
737 ms |
49376 KB |
Output is correct |
| 67 |
Correct |
1513 ms |
115816 KB |
Output is correct |
| 68 |
Correct |
1644 ms |
116132 KB |
Output is correct |
| 69 |
Correct |
543 ms |
18544 KB |
Output is correct |
| 70 |
Correct |
902 ms |
57584 KB |
Output is correct |
| 71 |
Correct |
1748 ms |
156944 KB |
Output is correct |
| 72 |
Correct |
1814 ms |
144004 KB |
Output is correct |
| 73 |
Correct |
827 ms |
42040 KB |
Output is correct |
| 74 |
Correct |
1703 ms |
118404 KB |
Output is correct |
| 75 |
Correct |
636 ms |
28328 KB |
Output is correct |
| 76 |
Correct |
1693 ms |
151640 KB |
Output is correct |
| 77 |
Correct |
1738 ms |
158776 KB |
Output is correct |
| 78 |
Correct |
598 ms |
25608 KB |
Output is correct |
| 79 |
Correct |
1462 ms |
115948 KB |
Output is correct |
| 80 |
Correct |
353 ms |
14948 KB |
Output is correct |
| 81 |
Correct |
896 ms |
55616 KB |
Output is correct |
| 82 |
Correct |
1805 ms |
146448 KB |
Output is correct |
| 83 |
Correct |
1725 ms |
118716 KB |
Output is correct |
| 84 |
Correct |
1678 ms |
118320 KB |
Output is correct |
| 85 |
Correct |
1726 ms |
118764 KB |
Output is correct |
| 86 |
Correct |
1804 ms |
119440 KB |
Output is correct |
| 87 |
Correct |
1789 ms |
119460 KB |
Output is correct |
