# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
139840 |
2019-08-01T14:09:05 Z |
Saboon |
Network (BOI15_net) |
C++14 |
|
24 ms |
23928 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 5e5 + 10;
int par[maxn], sz[maxn];
vector<int> t[maxn];
int cnt;
vector<int> a[maxn];
void DFS(int v, int par = -1){
bool leaf = 1;
for (auto u : t[v]){
if (u != par){
DFS(u, v);
leaf = 0;
}
if (par == -1)
cnt ++;
}
if (leaf){
a[cnt].push_back(v);
}
}
int dfs(int v, int par = -1){
for (auto u : t[v])
if (u != par)
sz[v] += dfs(u, v);
if (sz[v] == 0)
sz[v] = 1;
return sz[v];
}
int main(){
ios_base::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n - 1; i++){
int v, u;
cin >> v >> u;
t[v].push_back(u);
t[u].push_back(v);
}
if (n == 2)
return cout << 1 << endl << 1 << " " << 2 << endl, 0;
int root;
for (root = 1; root <= n; root ++)
if (t[root].size() > 1)
break;
dfs(root);
int v = root, Max = sz[root], parent = -1;
bool found = 1;
while (found){
found = 0;
for (auto u : t[v]){
if (u != parent and sz[u] >= Max / 2){
parent = v;
v = u;
found = 1;
break;
}
}
}
DFS(v);
vector<pair<int, int> > ans;
set<pair<int, int> > s;
for (int i = 0; i < cnt; i++){
int k = a[i].size();
s.insert({-k, i});
}
while (!s.empty()){
if (s.size() == 1){
int fi = (*s.begin()).second;
ans.push_back({a[fi].back(), v});
break;
}
int fi = (*s.begin()).second;
s.erase(s.begin());
int se = (*s.begin()).second;
s.erase(s.begin());
ans.push_back({a[fi].back(), a[se].back()});
a[fi].pop_back();
if (!a[fi].empty())
s.insert({-a[fi].size(), fi});
a[se].pop_back();
if (!a[se].empty())
s.insert({-a[se].size(), se});
}
cout << ans.size() << endl;
for (auto it : ans)
cout << it.first << " " << it.second << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23800 KB |
Output is correct |
2 |
Correct |
23 ms |
23800 KB |
Output is correct |
3 |
Correct |
24 ms |
23928 KB |
Output is correct |
4 |
Incorrect |
23 ms |
23800 KB |
Invalid number of links. |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23800 KB |
Output is correct |
2 |
Correct |
23 ms |
23800 KB |
Output is correct |
3 |
Correct |
24 ms |
23928 KB |
Output is correct |
4 |
Incorrect |
23 ms |
23800 KB |
Invalid number of links. |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23800 KB |
Output is correct |
2 |
Correct |
23 ms |
23800 KB |
Output is correct |
3 |
Correct |
24 ms |
23928 KB |
Output is correct |
4 |
Incorrect |
23 ms |
23800 KB |
Invalid number of links. |
5 |
Halted |
0 ms |
0 KB |
- |