#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int nmax = 500005;
vector<int>adj[nmax];
bool leaf[nmax]={0};
bool vis[nmax]={0};
vector<pair<int,int>>dist;
vector<pair<int,int>>daft;
void dfs(int x) {
stack<pair<int,int>>st;
st.push({x,1});
while(!st.empty()) {
int nod = st.top().fi;
int dis = st.top().se;
vis[nod]=true;
if(leaf[nod]) {
dist.push_back({dis,nod});
}
st.pop();
for(auto it:adj[nod]) {
if(vis[it]==false) {
st.push({it, dis+1});
}
}
}
return;
}
int main() {
int n,a,b;
cin >> n;
for(int i=1; i<n; i++) {
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int randole;
for(int i=1; i<=n; i++) {
if(adj[i].size()==1) {
leaf[i]=true;
randole=i;
}
}
dfs(randole);
sort(dist.begin(), dist.end());
int mid = dist.size()/2;
if(dist.size()%2==1) {
int j=mid+1;
for(int i=0; i<mid; i++) {
daft.push_back({dist[i].se, dist[j].se});
j++;
}
daft.push_back({dist[mid].se,dist[0].se});
} else {
int j = mid;
for(int i=0; i<mid; i++) {
daft.push_back({dist[i].se, dist[j].se});
j++;
}
}
cout << daft.size() << endl;
for(int i=0; i<daft.size(); i++) {
cout << daft[i].fi << " " << daft[i].se << endl;
}
return 0;
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0; i<daft.size(); i++) {
| ~^~~~~~~~~~~~
net.cpp:45:8: warning: 'randole' may be used uninitialized in this function [-Wmaybe-uninitialized]
45 | dfs(randole);
| ~~~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11968 KB |
Output is correct |
3 |
Correct |
6 ms |
12116 KB |
Output is correct |
4 |
Correct |
5 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
12000 KB |
Output is correct |
7 |
Correct |
6 ms |
12032 KB |
Output is correct |
8 |
Correct |
5 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Incorrect |
7 ms |
11988 KB |
Breaking single line is causing network to disconnect. |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11968 KB |
Output is correct |
3 |
Correct |
6 ms |
12116 KB |
Output is correct |
4 |
Correct |
5 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
12000 KB |
Output is correct |
7 |
Correct |
6 ms |
12032 KB |
Output is correct |
8 |
Correct |
5 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Incorrect |
7 ms |
11988 KB |
Breaking single line is causing network to disconnect. |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11968 KB |
Output is correct |
3 |
Correct |
6 ms |
12116 KB |
Output is correct |
4 |
Correct |
5 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
12000 KB |
Output is correct |
7 |
Correct |
6 ms |
12032 KB |
Output is correct |
8 |
Correct |
5 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Incorrect |
7 ms |
11988 KB |
Breaking single line is causing network to disconnect. |
11 |
Halted |
0 ms |
0 KB |
- |