# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
855239 |
2023-10-01T02:16:30 Z |
NeroZein |
Network (BOI15_net) |
C++17 |
|
2 ms |
13144 KB |
#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
const int N = 5e5 + 5;
int dep[N];
vector<int> g[N];
int dfs(int v, int p) {
int ret = v;
for (int u : g[v]) {
if (u != p) {
dep[u] = dep[v] + 1;
int t = dfs(u, v);
if (dep[t] > dep[ret]) {
ret = t;
}
}
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for(int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int a = dfs(1, 1);
dep[a] = 0;
int b = dfs(a, a);
assert(g[a].size() == 1 && g[b].size() == 1);
vector<pair<int, int>> ans = {{a, b}};
int t = -1;
for (int i = 1; i <= n; ++i) {
if ((int) g[i].size() > 1 || i == a || i == b) {
continue;
}
if (t == -1) {
t = i;
} else {
ans.emplace_back(t, i);
t = -1;
}
}
if (t != -1) {
ans.emplace_back(1, t);
}
cout << ans.size() << '\n';
for (auto [u, v] : ans) {
cout << u << ' ' << v << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12892 KB |
Output is correct |
2 |
Correct |
2 ms |
12888 KB |
Output is correct |
3 |
Correct |
2 ms |
12892 KB |
Output is correct |
4 |
Correct |
2 ms |
13144 KB |
Output is correct |
5 |
Correct |
2 ms |
12888 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
7 |
Correct |
2 ms |
12888 KB |
Output is correct |
8 |
Correct |
2 ms |
12892 KB |
Output is correct |
9 |
Correct |
2 ms |
12892 KB |
Output is correct |
10 |
Correct |
2 ms |
12888 KB |
Output is correct |
11 |
Correct |
2 ms |
12888 KB |
Output is correct |
12 |
Correct |
2 ms |
12892 KB |
Output is correct |
13 |
Correct |
2 ms |
12888 KB |
Output is correct |
14 |
Correct |
2 ms |
12892 KB |
Output is correct |
15 |
Correct |
2 ms |
12892 KB |
Output is correct |
16 |
Correct |
2 ms |
12888 KB |
Output is correct |
17 |
Correct |
2 ms |
12888 KB |
Output is correct |
18 |
Incorrect |
2 ms |
12892 KB |
Breaking single line is causing network to disconnect. |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12892 KB |
Output is correct |
2 |
Correct |
2 ms |
12888 KB |
Output is correct |
3 |
Correct |
2 ms |
12892 KB |
Output is correct |
4 |
Correct |
2 ms |
13144 KB |
Output is correct |
5 |
Correct |
2 ms |
12888 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
7 |
Correct |
2 ms |
12888 KB |
Output is correct |
8 |
Correct |
2 ms |
12892 KB |
Output is correct |
9 |
Correct |
2 ms |
12892 KB |
Output is correct |
10 |
Correct |
2 ms |
12888 KB |
Output is correct |
11 |
Correct |
2 ms |
12888 KB |
Output is correct |
12 |
Correct |
2 ms |
12892 KB |
Output is correct |
13 |
Correct |
2 ms |
12888 KB |
Output is correct |
14 |
Correct |
2 ms |
12892 KB |
Output is correct |
15 |
Correct |
2 ms |
12892 KB |
Output is correct |
16 |
Correct |
2 ms |
12888 KB |
Output is correct |
17 |
Correct |
2 ms |
12888 KB |
Output is correct |
18 |
Incorrect |
2 ms |
12892 KB |
Breaking single line is causing network to disconnect. |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12892 KB |
Output is correct |
2 |
Correct |
2 ms |
12888 KB |
Output is correct |
3 |
Correct |
2 ms |
12892 KB |
Output is correct |
4 |
Correct |
2 ms |
13144 KB |
Output is correct |
5 |
Correct |
2 ms |
12888 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
7 |
Correct |
2 ms |
12888 KB |
Output is correct |
8 |
Correct |
2 ms |
12892 KB |
Output is correct |
9 |
Correct |
2 ms |
12892 KB |
Output is correct |
10 |
Correct |
2 ms |
12888 KB |
Output is correct |
11 |
Correct |
2 ms |
12888 KB |
Output is correct |
12 |
Correct |
2 ms |
12892 KB |
Output is correct |
13 |
Correct |
2 ms |
12888 KB |
Output is correct |
14 |
Correct |
2 ms |
12892 KB |
Output is correct |
15 |
Correct |
2 ms |
12892 KB |
Output is correct |
16 |
Correct |
2 ms |
12888 KB |
Output is correct |
17 |
Correct |
2 ms |
12888 KB |
Output is correct |
18 |
Incorrect |
2 ms |
12892 KB |
Breaking single line is causing network to disconnect. |
19 |
Halted |
0 ms |
0 KB |
- |