Submission #1270522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270522		goldencheems	Spring cleaning (CEOI20_cleaning)	C++20	9 / 100	1096 ms	16064 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 17;
int n, q, r, c[N];
int ti, m, in[N], out[N], lg, p[N][21], d[N];
long long z1, z2;
vector <int> adj[N];
vector <pair <int, int>> leaf;
void dfs (int u, int pr)
{
    in[u] = ++ti, p[u][0] = pr, d[u] = d[pr] + 1;
    for (int i = 1; i <= lg; ++i)
    {
        p[u][i] = p[p[u][i - 1]][i - 1];
    }
    for (int v: adj[u])
    {
        if (v != pr)
        {
            dfs (v, u);
        }
    }
    if (adj[u].size() == 1)
    {
        leaf.push_back ({in[u], u});
        ++m;
    }
    out[u] = ti;
}
int lca (int u, int v)
{
    if (d[u] < d[v])
    {
        swap (u, v);
    }
    for (int i = lg; i >= 0; --i)
    {
        if (d[p[u][i]] >= d[v])
        {
            u = p[u][i];
        }
    }
    if (u == v)
    {
        return u;
    }
    for (int i = lg; i >= 0; --i)
    {
        if (p[u][i] != p[v][i])
        {
            u = p[u][i], v = p[v][i];
        }
    }
    return p[u][0];
}
int dist (int u, int v)
{
    return d[u] + d[v] - 2 * d[lca (u, v)];
}
void sub1()
{
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (i != r)
        {
            ++ans;
        }
    }
    while (q--)
    {
        int sz, z = m, _ = ans;
        cin >> sz;
        while (sz--)
        {
            int x;
            cin >> x;
            if (x == r)
            {
                ++z, ++ans;
                continue;
            }
            ++c[x], z += (c[x] > 1);
        }
        for (int i = 1; i <= n; ++i)
        {
            if (c[i] & 1)
            {
                ans += c[i];
            }
            else
            {
                ans += (c[i] > 0) * (c[i] + 1);
            }
            c[i] = 0;
        }
        if (z & 1)
        {
            cout << "-1\n";
        }
        else
        {
            cout << ans << "\n";
        }
        ans = _;
    }
}
void sub2()
{
    while (q--)
    {
        int sz;
        vector <int> vt;
        cin >> sz;
        for (int i = 1, x; i <= sz; ++i)
        {
            cin >> x;
            adj[x].push_back(n + i);
            adj[n + i].push_back(x);
            vt.push_back(x);
        }
        m = ti = 0, lg = __lg(n + sz);
        dfs (r, 0);
        if (m & 1)
        {
            cout << "-1\n";
        }
        else
        {
            sort (leaf.begin(), leaf.end());
            z2 = dist (leaf[0].second, leaf[m - 1].second);
            for (int i = 1; i < m; i += 2)
            {
                z1 += dist (leaf[i].second, leaf[i - 1].second);
            }
            for (int i = 2; i < m - 1; i += 2)
            {
                z2 += dist (leaf[i].second, leaf[i - 1].second);
            }
            cout << min (z1, z2) << "\n";
        }
        leaf.clear();
        for (int x: vt)
        {
            adj[x].pop_back();
        }
        for (int i = 1; i <= sz; ++i)
        {
            adj[n + i].clear();
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for (int i = 1, u, v; i < n; ++i)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (adj[i].size() > 1)
        {
            r = i;
            continue;
        }
        ++m;
    }
    if (m >= n - 1)
    {
        sub1();
        return 0;
    }
    sub2();
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30