# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
79597 |
2018-10-15T04:47:22 Z |
EntityIT |
Network (BOI15_net) |
C++14 |
|
14 ms |
12396 KB |
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef pair<int, int> ii;
const int N = 5e5 + 5;
int n, child[N], nLeaf;
vector<int> gr[N], vec;
void prep (int u, int p) {
for (int v : gr[u]) if (v != p) {
prep(v, u);
child[u] += child[v];
}
child[u] += (gr[u].size() == 1);
}
int findCentroid (int u, int p) {
for (int v : gr[u]) if (v != p) {
if (child[v] > (nLeaf + 1) / 2 ) return findCentroid(v, u);
}
return u;
}
void dfs (int u, int p) {
for (int v : gr[u]) if (v != p) dfs(v, u);
if (gr[u].size() == 1) vec.pb(u);
}
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int _ = 1; _ < n; ++_) {
int u, v; cin >> u >> v;
gr[u].pb(v); gr[v].pb(u);
}
for (int u = 1; u <= n; ++u) nLeaf += (gr[u].size() == 1);
cout << (nLeaf + 1) / 2 << '\n';
prep(1, 1);
int cen = findCentroid(1, 1);
for (int u : gr[cen]) dfs(u, cen);
for (int i = 0; i < vec.size() - (nLeaf + 1) / 2; ++i) {
cout << vec[i] << ' ' << vec[ i + (nLeaf + 1) / 2 ] << '\n';
}
if (nLeaf % 2) cout << vec[0] << ' ' << vec[nLeaf / 2];
return 0;
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size() - (nLeaf + 1) / 2; ++i) {
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
12152 KB |
Output is correct |
2 |
Correct |
12 ms |
12396 KB |
Output is correct |
3 |
Correct |
14 ms |
12396 KB |
Output is correct |
4 |
Correct |
13 ms |
12396 KB |
Output is correct |
5 |
Correct |
13 ms |
12396 KB |
Output is correct |
6 |
Correct |
12 ms |
12396 KB |
Output is correct |
7 |
Incorrect |
13 ms |
12396 KB |
Unexpected end of file - int32 expected |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
12152 KB |
Output is correct |
2 |
Correct |
12 ms |
12396 KB |
Output is correct |
3 |
Correct |
14 ms |
12396 KB |
Output is correct |
4 |
Correct |
13 ms |
12396 KB |
Output is correct |
5 |
Correct |
13 ms |
12396 KB |
Output is correct |
6 |
Correct |
12 ms |
12396 KB |
Output is correct |
7 |
Incorrect |
13 ms |
12396 KB |
Unexpected end of file - int32 expected |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
12152 KB |
Output is correct |
2 |
Correct |
12 ms |
12396 KB |
Output is correct |
3 |
Correct |
14 ms |
12396 KB |
Output is correct |
4 |
Correct |
13 ms |
12396 KB |
Output is correct |
5 |
Correct |
13 ms |
12396 KB |
Output is correct |
6 |
Correct |
12 ms |
12396 KB |
Output is correct |
7 |
Incorrect |
13 ms |
12396 KB |
Unexpected end of file - int32 expected |
8 |
Halted |
0 ms |
0 KB |
- |