# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
42248 |
2018-02-24T05:52:08 Z |
5ak0 |
Network (BOI15_net) |
C++14 |
|
14 ms |
12772 KB |
/*
ID: 5ak0
PROG:
LANG: C++11
*/
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN =500010;
bool u[MAXN];
vector <int> g[MAXN], vec;
queue <pii> q;
int n, a, b;
void dfs(int v){
u[v] = 1;
bool ok = 1;
for (auto to : g[v]){
if (u[to] == 0){
ok = 0;
dfs(to);
}
}
if (ok == 1)
vec.pb(v);
}
int main(){
ios_base::sync_with_stdio(0);
#ifndef SAKO
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
#endif // SAKO
cin >> n;
for (int i = 1; i < n; ++i){
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
int root = 1;
while (root <= n && g[root].size() == 1)
++root;
dfs(root);
memset(u, 0, sizeof(u));
for (int i = 0; i < vec.size(); ++i){
if (u[vec[i]] == 0){
if (i + 1 < vec.size())
q.push({vec[i], vec[i + 1]}), u[vec[i + 1]] = 1;
else{
if (0 < i - 1)
q.push({vec[i], vec[i - 1]}), u[vec[i]] = 1, u[vec[i - 1]] = 1;
else
q.push({vec[i], root}), u[vec[i]] = 1;
}
}
}
cout << q.size() << "\n";
while (!q.empty()){
cout << q.front().fr << " " << q.front().sc << "\n";
q.pop();
}
return 0;
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); ++i){
^
net.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i + 1 < vec.size())
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
12536 KB |
Output is correct |
2 |
Incorrect |
11 ms |
12772 KB |
Breaking single line is causing network to disconnect. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
12536 KB |
Output is correct |
2 |
Incorrect |
11 ms |
12772 KB |
Breaking single line is causing network to disconnect. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
12536 KB |
Output is correct |
2 |
Incorrect |
11 ms |
12772 KB |
Breaking single line is causing network to disconnect. |
3 |
Halted |
0 ms |
0 KB |
- |