# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
821955 |
2023-08-12T00:20:23 Z |
exodus_ |
Network (BOI15_net) |
C++14 |
|
8 ms |
12092 KB |
#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]==true) {
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 random = -1;
for(int i=1; i<=n; i++) {
if(adj[i].size()==1) {
leaf[i]=true;
if(random==-1) random = i;
}
}
dfs(random);
sort(dist.begin(), dist.end());
int mid = dist.size()/2;
cout << (dist.size()+1)/2 << endl;
for(int i=0; i<mid; i++) {
cout << dist[i].se << " " << dist[i+mid].se << endl;
}
if(dist.size()%2==1) {
cout << dist[0].se << " " << dist[dist.size()-1].se << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
12052 KB |
Output is correct |
3 |
Correct |
7 ms |
12048 KB |
Output is correct |
4 |
Correct |
7 ms |
12048 KB |
Output is correct |
5 |
Correct |
7 ms |
12092 KB |
Output is correct |
6 |
Correct |
7 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
8 ms |
12048 KB |
Output is correct |
12 |
Incorrect |
7 ms |
11988 KB |
Breaking single line is causing network to disconnect. |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
12052 KB |
Output is correct |
3 |
Correct |
7 ms |
12048 KB |
Output is correct |
4 |
Correct |
7 ms |
12048 KB |
Output is correct |
5 |
Correct |
7 ms |
12092 KB |
Output is correct |
6 |
Correct |
7 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
8 ms |
12048 KB |
Output is correct |
12 |
Incorrect |
7 ms |
11988 KB |
Breaking single line is causing network to disconnect. |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
12052 KB |
Output is correct |
3 |
Correct |
7 ms |
12048 KB |
Output is correct |
4 |
Correct |
7 ms |
12048 KB |
Output is correct |
5 |
Correct |
7 ms |
12092 KB |
Output is correct |
6 |
Correct |
7 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
8 ms |
12048 KB |
Output is correct |
12 |
Incorrect |
7 ms |
11988 KB |
Breaking single line is causing network to disconnect. |
13 |
Halted |
0 ms |
0 KB |
- |