| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 79572 |
2018-10-15T03:27:40 Z |
Vinhspm |
Network (BOI15_net) |
C++14 |
|
15 ms |
12392 KB |
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
const int N = 5e5 + 10;
const int oo = 1e9;
int n;
int deg[N], sz[N], tmp[N];
bool visit[N];
vector<int> lef, rig, vi[N];
void dfs(int pre, int u) {
sz[u] = 1;
for(int v: vi[u]) if(v != pre)
dfs(u, v), sz[u] += sz[v];
// :D
}
void findcen(int pre, int u, int sz1, bool spm) {
if(spm) visit[u] = true;
if(!spm) {
for(int v: vi[u]) if(v != pre && sz[v] * 2 >= sz1) {
findcen(u, v, sz1, 0);
return;
}
}
visit[u] = true;
for(int v: vi[u]) if(v != pre) findcen(u, v, sz1, 1);
}
void calc(int pos, bool spm) {
int cnt = 0;
for(int i = pos; i <= n; ++i) if(visit[i] == spm && deg[i] == 1)
tmp[++cnt] = i;
for(int i = 1; i <= cnt - 1; i += 2) cout << tmp[i] << ' ' << tmp[i + 1] << '\n';
if(cnt % 2 == 1) for(int i = 1; i <= n; ++i) if(visit[i] == 1 - spm && deg[i] == 1) {
cout << i << ' ' << tmp[cnt]; exit(0);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
vi[u].pb(v); vi[v].pb(u);
deg[u] ++; deg[v] ++;
}
int ans = 0;
for(int i = 1; i <= n; ++i) if(deg[i] == 1) ans ++;
dfs(1, 1);
findcen(1, 1, sz[1], 0);
cout << (ans + 1) / 2 << '\n';
int ptr1 = 1, ptr2 = 1;
while(visit[ptr1] || deg[ptr1] > 1) ptr1 ++;
while(!visit[ptr2] || deg[ptr2] > 1) ptr2 ++;
while(ptr1 <= n && ptr2 <= n) {
cout << ptr1 << ' ' << ptr2 << '\n';
ptr1 ++; ptr2 ++;
while((visit[ptr1] || deg[ptr1] != 1)) {
ptr1 ++;
if(ptr1 > n) break;
}
while((!visit[ptr2] || deg[ptr2] != 1)) {
ptr2 ++;
if(ptr2 > n) break;
}
}
if(ptr1 <= n) calc(ptr1, 0);
if(ptr2 <= n) calc(ptr2, 1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12024 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12276 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12276 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12276 KB |
Output is correct |
| 5 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 6 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 7 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 8 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 9 |
Correct |
13 ms |
12348 KB |
Output is correct |
| 10 |
Correct |
12 ms |
12348 KB |
Output is correct |
| 11 |
Correct |
12 ms |
12348 KB |
Output is correct |
| 12 |
Correct |
12 ms |
12364 KB |
Output is correct |
| 13 |
Correct |
15 ms |
12364 KB |
Output is correct |
| 14 |
Correct |
13 ms |
12364 KB |
Output is correct |
| 15 |
Correct |
13 ms |
12364 KB |
Output is correct |
| 16 |
Correct |
13 ms |
12392 KB |
Output is correct |
| 17 |
Correct |
13 ms |
12392 KB |
Output is correct |
| 18 |
Incorrect |
12 ms |
12392 KB |
Breaking single line is causing network to disconnect. |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12024 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12276 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12276 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12276 KB |
Output is correct |
| 5 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 6 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 7 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 8 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 9 |
Correct |
13 ms |
12348 KB |
Output is correct |
| 10 |
Correct |
12 ms |
12348 KB |
Output is correct |
| 11 |
Correct |
12 ms |
12348 KB |
Output is correct |
| 12 |
Correct |
12 ms |
12364 KB |
Output is correct |
| 13 |
Correct |
15 ms |
12364 KB |
Output is correct |
| 14 |
Correct |
13 ms |
12364 KB |
Output is correct |
| 15 |
Correct |
13 ms |
12364 KB |
Output is correct |
| 16 |
Correct |
13 ms |
12392 KB |
Output is correct |
| 17 |
Correct |
13 ms |
12392 KB |
Output is correct |
| 18 |
Incorrect |
12 ms |
12392 KB |
Breaking single line is causing network to disconnect. |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12024 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12276 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12276 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12276 KB |
Output is correct |
| 5 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 6 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 7 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 8 |
Correct |
12 ms |
12324 KB |
Output is correct |
| 9 |
Correct |
13 ms |
12348 KB |
Output is correct |
| 10 |
Correct |
12 ms |
12348 KB |
Output is correct |
| 11 |
Correct |
12 ms |
12348 KB |
Output is correct |
| 12 |
Correct |
12 ms |
12364 KB |
Output is correct |
| 13 |
Correct |
15 ms |
12364 KB |
Output is correct |
| 14 |
Correct |
13 ms |
12364 KB |
Output is correct |
| 15 |
Correct |
13 ms |
12364 KB |
Output is correct |
| 16 |
Correct |
13 ms |
12392 KB |
Output is correct |
| 17 |
Correct |
13 ms |
12392 KB |
Output is correct |
| 18 |
Incorrect |
12 ms |
12392 KB |
Breaking single line is causing network to disconnect. |
| 19 |
Halted |
0 ms |
0 KB |
- |
