# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
797479 |
2023-07-29T12:42:51 Z |
bonk |
Network (BOI15_net) |
C++14 |
|
7 ms |
12060 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 2;
vector<int>adj[N];
vector<pair<int, int>>t;
int timer = 0;
void dfs(int prev, int cur){
timer++;
bool leaf = true;
for(auto &nxt: adj[cur]){
if(prev == nxt) continue;
leaf = false;
dfs(cur, nxt);
}
if(leaf) t.emplace_back(timer, cur);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
for(int i = 0; i < n - 1; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bool tmp = false;
for(int i = 1; i <= n; i++){
if(adj[i].size() > 1){
dfs(-1, i);
break;
}
}
sort(t.begin(), t.end());
cout << (t.size() + 1)/2 << '\n';
int l = 0, r = t.size() - 1;
while(l < r){
cout << t[l].second << " " << t[r].second << '\n';
l++; r--;
}
if(l == r){
cout << t[l].second << " " << t.back().second << '\n';
}
return 0;
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:31:10: warning: unused variable 'tmp' [-Wunused-variable]
31 | bool tmp = false;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12060 KB |
Output is correct |
2 |
Incorrect |
6 ms |
12044 KB |
Breaking single line is causing network to disconnect. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12060 KB |
Output is correct |
2 |
Incorrect |
6 ms |
12044 KB |
Breaking single line is causing network to disconnect. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12060 KB |
Output is correct |
2 |
Incorrect |
6 ms |
12044 KB |
Breaking single line is causing network to disconnect. |
3 |
Halted |
0 ms |
0 KB |
- |