Submission #468446

#	Time	Username	Problem	Language	Result	Execution time	Memory
468446		blue	Spring cleaning (CEOI20_cleaning)	C++17	34 / 100	1098 ms	22372 KiB

cleaning

#include <iostream>
#include <vector>
using namespace std;

int N;
int Q;

vector< vector<int> > E;
vector< vector<int> > edge;

vector<int> leafcount;
vector<int> visit;

void dfs(int u)
{
    if(edge[u].size() == 1)
    {
        leafcount[u] = 1;
    }
    else
    {
        leafcount[u] = 0;
        for(int v: edge[u])
        {
            if(visit[v]) continue;
            visit[v] = 1;
            dfs(v);
            leafcount[u] += leafcount[v];
        }
    }
}

int main()
{
    cin >> N >> Q;
    E = vector< vector<int> >(N, vector<int>(0));

    for(int e = 1; e <= N-1; e++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        E[u].push_back(v);
        E[v].push_back(u);
    }

    for(int q = 1; q <= Q; q++)
    {
        edge = E;

        int D;
        cin >> D;

        for(int x = 0; x < D; x++)
        {
            int a;
            cin >> a;
            a--;

            edge[a].push_back(N+x);
            edge.push_back(vector<int>(1, a));
        }

        if(N == 1 && D == 1)
        {
            cout << 1 << '\n';
        }
        else
        {
            N += D;

            leafcount = vector<int>(N, 0);
            visit = vector<int>(N, 0);

            int rt = 0;
            while(edge[rt].size() == 1)
                rt++;

            visit[rt] = 1;
            dfs(rt);

            if(leafcount[rt] % 2 == 1)
            {
                cout << "-1\n";
            }
            else
            {
                int res = 0;
                for(int i = 0; i < N; i++)
                {
                    if(i == rt) continue;
                    if(leafcount[i] % 2 == 0)
                        res += 2;
                    else
                        res += 1;
                }

                cout << res << '\n';
            }

            N -= D;
        }
    }
}

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