I had a 1 character bug on https://codeforces.me/contest/1396/problem/E in contest, and was just a tiny bit too slow to fix it. So now I'm sharing my story in hopes of collecting pity and contribution. See if you can find the bug faster than I did :)
The submission I made: (timestamp 1:56:00) https://codeforces.me/contest/1396/my
I found the fix & saved it at exactly 09:35:01: ~~~~~ ~/codeforces/666div1 ls -lT e.cpp -rw-r--r-- 1 stevenhao staff 4107 Aug 30 09:35:01 2020 e.cpp ~~~~~
Here is the code, before the fix:
// ============= Solution ============= //
int main() {
int n;
ll k;
cin >> n >> k;
vector<vector<int>> ed(n + 1);
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
--a, --b;
ed[a].push_back(b);
ed[b].push_back(a);
}
vector<int> subtreesize(n, 1);
auto go1 = yc([&](auto dfs, int cur, int prv = -1) -> void {
for (int nxt: ed[cur]) {
if (nxt == prv) continue;
dfs(nxt, cur);
subtreesize[cur] += subtreesize[nxt];
}
});
go1(0);
for (int i: subtreesize) {
k -= i % 2;
}
if (k % 2 == 1) {
cout << "NO\n";
return 0;
}
vector<pii> matches;
ed[n++].push_back(0); // new root
vector<vector<int>> buffers(n);
pp(k);
auto go2 = yc([&](auto dfs, int cur, int prv = -1) -> vector<int>& {
pp(cur, k);
vector<int> &res = buffers[cur];
res.push_back(cur);
for (int nxt: ed[cur]) {
if (nxt == prv) continue;
vector<int> &bb = dfs(nxt, cur);
k -= sz(bb) / 2 * 2;
while (sz(bb) >= 2 && k < 0) {
matches.push_back(pii(bb[sz(bb) - 2], bb[sz(bb) - 1]));
bb.pop_back();
bb.pop_back();
k += 2;
}
if (sz(res) < sz(bb)) {
swap(res, bb);
}
for (int i: bb) {
res.push_back(i);
}
}
return res;
});
vector<int> final_output = go2(n - 1);
if (k > 0) {
cout << "NO\n";
} else {
pp(k);
cout << "YES\n";
for (pii p: matches) {
cout << p.fi + 1 << " " << p.se + 1 << "\n";
}
}
}
The bug is...