Submission #1270526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270526		goldencheems	Spring cleaning (CEOI20_cleaning)	C++20	9 / 100	41 ms	12332 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fti(i, x, y) for (int i = x; i <= y; ++i)
#define F first
#define S second

const int MA = 1e5 + 10;

int n, q, in[MA], D[MA], dp[MA];
bool leaf[MA], s1 = 1;
vector <int> c[MA], con[MA], con1[MA];

void sub1()
{
    int leaves = n - 1;
    fti(Q, 1, q)
    {
        unordered_map <int, int> mp;
        int cnt = leaves, res = n - 1;
        for (int x : c[Q])
        {
            ++mp[x]; if (mp[x] > 1) ++cnt;
        }
        if (cnt & 1)
        {
            cout << -1 << '\n'; continue;
        }
        res = n + D[Q] - 1;
        for (auto x : mp)
        {
            int f = x.S;
            res += (f - 1) % 2;
        }
        cout << res << '\n';
    }
}

int sz[MA];

void dfs(ll u, ll p)
{
    dp[u] = leaf[u];
    for (int v : con1[u])
    {
        if (v == p) continue;
        dfs(v, u); dp[u] += (dp[v] - 1) % 2;
    }
}

void sub2()
{
    int root = 0;
    fti(i, 1, n)
        if (!leaf[i])
        {
            root = i; break;
        }
    fti(Q, 1, q)
    {
        int cnt = accumulate(leaf + 1, leaf + n + 1, 0);
        ll nd = n;
        fti(i, 1, n) con1[i].clear();
        fti(i, 1, n)
            for (int x : con[i]) con1[i].push_back(x);
        unordered_map <int, int> mp;
        for (int x : c[Q])
        {
            con1[++nd].push_back(x);
            con1[x].push_back(nd);
            if (mp[x] > 1) ++cnt;
        }
        if (cnt & 1)
        {
            cout << -1 << '\n'; continue;
        }
        fti(i, 1, n + D[Q]) dp[i] = 0;
        dfs(root, 0);
        cout << dp[root] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    fti(i, 1, n - 1)
    {
        int u, v; cin >> u >> v;
        ++in[u], ++in[v];
        con[u].push_back(v);
        con[v].push_back(u);
    }
    fti(i, 1, q)
    {
        cin >> D[i];
        fti(j, 1, D[i])
        {
            int x; cin >> x; c[i].push_back(x);
            s1 &= (x != 1);
        }
    }
    fti(i, 1, n) leaf[i] = (in[i] == 1);
//    cerr << accumulate(leaf + 1, leaf + n + 1, 0);
    if (s1 && in[1] == n - 1)
        sub1();
//    else
//        sub2();
    return 0;
}

/**
5 3
1 2
1 3
1 4
1 5
9 3 3 4 4 4 5 5 5 5
7 2 2 3 3 3 5 5
2 2 2

7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1

7 3
1 2
2 4
4 5
5 6
5 7
3 4
4 1 1 2 6
3 6 6 2
2 2 7
*/

• 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