# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1235274 | badge881 | Spring cleaning (CEOI20_cleaning) | C++20 | 1096 ms | 10820 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N = 100000;
vector<vector<int>> adj;
vector<int> parity, anc, cost = {2, 1};
int total_cost = 0;
int count_leaves(int u, int a)
{
int s = 0;
for (auto v : adj[u])
{
if (v != a)
{
anc[v] = u;
s += count_leaves(v, u);
}
}
if (s == 0)
s = 1;
total_cost += cost[s % 2];
parity[u] = s % 2;
return s;
}
void flip(int u)
{
total_cost -= cost[parity[u]];
parity[u] ^= 1;
total_cost += cost[parity[u]];
if (anc[u] != -1)
flip(anc[u]);
}
signed main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, q;
scanf("%lld%lld\n", &n, &q);
adj.resize(n);
parity.resize(n);
anc.resize(n, -1);
int node = 0;
int deg = 0;
for (int i = 0; i < n - 1; i++)
{
int a, b;
scanf("%lld%lld\n", &a, &b);
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
if (adj[a].size() > deg)
{
node = a;
deg = adj[a].size();
}
if (adj[b].size() > deg)
{
node = b;
deg = adj[b].size();
}
}
int r = count_leaves(node, -1);
for (int i = 0; i < q; i++)
{
int d;
scanf("%lld\n", &d);
vector<int> parents;
for (int j = 0; j < d; j++)
{
int v;
scanf("%lld\n", &v);
v--;
parents.push_back(v);
adj[parents.back()].push_back(adj.size());
total_cost++;
if (adj[parents.back()].size() > 2)
{
flip(parents.back());
r ^= 1;
}
}
if (parity[node] == 1)
printf("-1\n");
else
printf("%lld\n", total_cost - 2);
adj.resize(n);
for (auto e : parents)
{
if (adj[e].size() > 2)
{
flip(e);
r ^= 1;
}
total_cost--;
adj[e].pop_back();
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |