| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 629983 |
2022-08-15T13:14:02 Z |
MinaRagy06 |
Network (BOI15_net) |
C++17 |
|
1 ms |
324 KB |
#include <bits/stdc++.h>
using namespace std;
#define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl '\n'
#define int long long
vector<vector<int>> adj;
int pos, mx = -1e18;
void dfs2(int i, int sum, int par)
{
if (sum >= mx) mx = sum ,pos = i;
for (auto nxt : adj[i]) if (nxt != par) dfs2(nxt, sum+1, i);
}
vector<pair<int, int>> dfs(int i, int par)
{
if (adj[i].size() ==1) return {{0ll, i}};
vector<pair<int, int>> ret;
for (auto nxt : adj[i]) if (nxt != par)
{
vector<pair<int,int>> x = dfs(nxt ,i);
for (auto &j : x) j.first++;
ret.insert(ret.end(), x.begin(), x.end());
}
return ret;
}
signed main()
{
lesgooo;
int n, u, v;
cin >> n;
adj.resize(n);
for (int i = 0; i < n-1; i++) cin >> u >> v, adj[--u].push_back(--v), adj[v].push_back(u);
int idx = 0; mx = 0;
for (int i = 0; i < n; i++) if ((int)adj[i].size() > mx) idx = i, mx = adj[i].size();
vector<vector<pair<int,int>>> a;
for (auto nxt : adj[idx]) a.push_back(dfs(nxt, idx));
for (int i = 0; i < (int)a.size(); i++) sort(a[i].begin(), a[i].end());
set<int> leaf;
for (int i = 0; i < n; i++) if (adj[i].size() == 1) leaf.insert(i);
vector<vector<int>> ans;
while (1)
{
set<vector<int>> s;
for (int i = 0; i < (int)a.size(); i++) if ((int)a[i].size()) s.insert({-a[i].back().first, a[i].back().second, i});
if (s.empty()) break;
if (s.size() == 1) break;
vector<int> x = *s.begin(), y;
s.erase(s.begin());
y = *s.begin();
a[x[2]].pop_back(), a[y[2]].pop_back();
leaf.erase(x[1]), leaf.erase(y[1]);
ans.push_back({x[1]+1, y[1]+1});
}
while (leaf.size() > 1)
{
int x = *leaf.begin(), y;
leaf.erase(leaf.begin());
y = *leaf.begin();
leaf.erase(leaf.begin());
ans.push_back({x+1, y+1});
}
if (leaf.size()) dfs2((*leaf.begin()), 0, -1), ans.push_back({(*leaf.begin())+1, pos+1});
cout << ans.size() << endl;
for (auto i : ans) cout << i[0] << " " << i[1] << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
324 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Incorrect |
0 ms |
320 KB |
Breaking single line is causing network to disconnect. |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
324 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Incorrect |
0 ms |
320 KB |
Breaking single line is causing network to disconnect. |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
324 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Incorrect |
0 ms |
320 KB |
Breaking single line is causing network to disconnect. |
| 16 |
Halted |
0 ms |
0 KB |
- |
