| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 104659 |
2019-04-08T15:01:35 Z |
Anai |
Network (BOI15_net) |
C++14 |
|
15 ms |
12160 KB |
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using pii = pair<int, int>;
const int N = 5e5 + 5;
vector<int> g[N];
int st[N], dr[N], aib[N], line[N], aux[N];
bool matched[N];
vector<pii> ant;
set<pii> leaves;
int n, root, connector;
static int lsb(const int &x) {
return x & -x; }
static int query(int pos) {
int ant = 0;
for (; pos > 0; pos-= lsb(pos))
ant+= aib[pos];
return ant; }
static void update(int pos, int val) {
for (; pos < N; pos+= lsb(pos))
aib[pos]+= val; }
static void dfs(int u) {
static int lptr = 0; ++lptr;
line[lptr] = u;
st[u] = lptr;
for (auto v: g[u]) {
g[v].erase(remove(begin(g[v]), end(g[v]), u), end(g[v]));
dfs(v); }
dr[u] = lptr; }
static void solve(int u) {
if (g[u].empty()) // I'm a leaf
return;
aux[u] = query(dr[u]) - query(st[u] - 1);
for (auto v: g[u])
aux[v] = query(dr[v]) - query(st[v] - 1);
g[u].erase(remove_if(begin(g[u]), end(g[u]), [&](const int &nod) { return aux[nod] == 0; }), end(g[u])); // remove solved subtrees
if (g[u].size() == 1) { // I'm an intermediar
solve(g[u][0]);
return; }
if (aux[u] % 2) { // get read of the odd case (remove one, ignore other ---- may only happen at root)
int a = g[u][0], b = g[u][1];
auto ita = leaves.lower_bound(pii(st[a], 0));
auto itb = leaves.lower_bound(pii(st[b], 0));
ant.emplace_back(ita->second, itb->second);
update(ita->first, -1);
leaves.erase(ita);
aux[a]-= 1;
solve(u);
return; }
sort(begin(g[u]), end(g[u]), [&](const int &a, const int &b) {
return aux[a] > aux[b]; });
for (int i = 0; i + 1 < g[u].size(); i+= 2) { // pair consecutive elements
int a = g[u][i], b = g[u][i + 1];
auto ita = leaves.lower_bound(pii(st[a], 0));
auto itb = leaves.lower_bound(pii(st[b], 0));
ant.emplace_back(ita->second, itb->second);
update(ita->first, -1);
update(itb->first, -1);
leaves.erase(ita);
leaves.erase(itb);
aux[a]-= 1;
aux[b]-= 1; }
if (g[u].size() % 2 == 1) { // pair the last one left if it's the case
int a = g[u].rbegin()[0], b = g[u][0];
auto ita = leaves.lower_bound(pii(st[a], 0));
auto itb = leaves.lower_bound(pii(st[b], 0));
ant.emplace_back(ita->second, itb->second);
update(ita->first, -1);
update(itb->first, -1);
leaves.erase(ita);
leaves.erase(itb);
aux[a]-= 1;
aux[b]-= 1; }
g[u].erase(remove_if(begin(g[u]), end(g[u]), [&](const int &nod) { return aux[nod] == 0; }), end(g[u])); // get rid of solved ones
auto it = partition(begin(g[u]), end(g[u]), [&](const int &nod) { return aux[nod] % 2; });
for (int i = 0; i + 1 < g[u].size() && aux[g[u][i + 1]] % 2 == 1; i+= 2) { // make the odds even
int a = g[u][i], b = g[u][i + 1];
auto ita = leaves.lower_bound(pii(st[a], 0));
auto itb = leaves.lower_bound(pii(st[b], 0));
ant.emplace_back(ita->second, itb->second);
update(ita->first, -1);
update(itb->first, -1);
leaves.erase(ita);
leaves.erase(itb);
aux[a]-= 1;
aux[b]-= 1; }
sort(begin(g[u]), end(g[u]), [&](const int &a, const int &b) {
return aux[a] < aux[b]; });
for (int i = 0; i + 1 < g[u].size(); i+= 2) {
int a = g[u][i], b = g[u][i + 1];
while (aux[a] && aux[b]) {
auto ita = leaves.lower_bound(pii(st[a], 0));
auto itb = leaves.lower_bound(pii(st[b], 0));
ant.emplace_back(ita->second, itb->second);
update(ita->first, -1);
update(itb->first, -1);
leaves.erase(ita);
leaves.erase(itb);
aux[a]-= 1;
aux[b]-= 1; } }
for (auto v: g[u])
solve(v); }
int main() {
#ifdef HOME
freopen("network.in", "r", stdin);
freopen("network.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int u, v, i = 1; i < n; ++i) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u); }
for (root = 1; g[root].size() == 1; ++root);
dfs(root);
for (int i = 1; i <= n; ++i)
if (g[i].empty()) {
leaves.emplace(st[i], i);
update(st[i], 1); }
int l = leaves.size();
solve(root);
assert(ant.size() == (l + 1) / 2);
cout << ant.size() << '\n';
for (auto i: ant)
cout << i.x << ' ' << i.y << '\n';
return 0; }
Compilation message
net.cpp: In function 'void solve(int)':
net.cpp:70:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i + 1 < g[u].size(); i+= 2) { // pair consecutive elements
~~~~~~^~~~~~~~~~~~~
net.cpp:101:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i + 1 < g[u].size() && aux[g[u][i + 1]] % 2 == 1; i+= 2) { // make the odds even
~~~~~~^~~~~~~~~~~~~
net.cpp:118:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i + 1 < g[u].size(); i+= 2) {
~~~~~~^~~~~~~~~~~~~
net.cpp:99:7: warning: variable 'it' set but not used [-Wunused-but-set-variable]
auto it = partition(begin(g[u]), end(g[u]), [&](const int &nod) { return aux[nod] % 2; });
^~
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from net.cpp:1:
net.cpp: In function 'int main()':
net.cpp:160:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(ant.size() == (l + 1) / 2);
~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12160 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
12160 KB |
Breaking single line is causing network to disconnect. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12160 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
12160 KB |
Breaking single line is causing network to disconnect. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12160 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
12160 KB |
Breaking single line is causing network to disconnect. |
| 3 |
Halted |
0 ms |
0 KB |
- |
