Submission #965236

#	Time	Username	Problem	Language	Result	Execution time	Memory
965236		RaulAndrei01	Spring cleaning (CEOI20_cleaning)	C++17	16 / 100	1071 ms	30708 KiB

cleaning

#include<iostream>
#include<vector>
#include<cassert>

using namespace std;
const int NMAX = 1e5;
vector<int> adj[2 * NMAX+1];
int leafes[NMAX+1];
int root = -1;
int ans;

void dfs (int nod , int par)
{
    if (adj[nod].size() <= 1) leafes[nod] = 1;
    else leafes[nod] = 0;
    for (auto &to : adj[nod])
    {
        if (to != par) {
            dfs(to , nod);
            leafes[nod] += leafes[to];
        }
    }
    if (leafes[nod] % 2 == 0 && nod != root) ans++;
}

int main ()
{
    int n , q; cin >> n >> q;
    for (int i = 2; i <= n; i++)
    {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    
    for (int i = 1; i <= n; i++)
    {
        if (adj[i].size() > 1) root = i;
    }
    assert(root != -1);
    while (q--)
    {
        int d; cin >> d;
        vector<int> a(d);
        for (int i = 0; i < d; i++)
        {
            cin >> a[i];
            adj[a[i]].push_back(n+i+1);
        }

        ans = 0;
        dfs(root , 0);
        cout << ((leafes[root] % 2 == 0) ? n + d - 1 + ans : -1) << '\n';

        for (int i = 0; i < d; i++)
        {
            adj[a[i]].pop_back();
        }
    }

    return 0;
}

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