Submission #1166837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166837		dragst	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1095 ms	25276 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

pair<long long, long long> dp[200005];
long long p[200005], leaf[200005];
vector<long long> adj[200005], vv;

void dfs(long long x)
{
    dp[x]=make_pair(0LL, 0LL);
    if (adj[x].size()==1) {leaf[x]=1;}
    else {leaf[x]=0;};
    for (auto y: adj[x])
    {
        if (y!=p[x])
        {
            p[y]=x;
            dfs(y);
            dp[x].first+=dp[y].first+dp[y].second;
            dp[x].second+=dp[y].second;
            dp[x].second%=2;
            if (dp[x].second==0) {dp[x].second=2;};
        };
    };
    if (x>1 && leaf[x]) {dp[x].second=1;};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	long long n, q, i, u, v;
	cin >> n >> q;
	for (i=1; i<n; i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    };
    dfs(1);
    while (q--)
    {
        cin >> i;
        v=n+1;
        while (i--)
        {
            cin >> u;
            vv.push_back(u);
            adj[u].push_back(v);
            adj[v].push_back(u);
            v++;
        };
        dfs(1);
        if (leaf[1]==1 && dp[1].second==2) {cout << -1 << "\n";}
        else if (leaf[1]==0 && dp[1].second==1) {cout << -1 << "\n";}
        else {cout << dp[1].first << "\n";};
        while (!vv.empty())
        {
            adj[adj[vv.back()].back()].pop_back();
            adj[vv.back()].pop_back();
            vv.pop_back();
        };
    };
}

• 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