Submission #1150735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150735		vladilius	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1096 ms	20484 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, q; cin>>n>>q;
    vector<pii> ed;
    for (int i = 1; i < n; i++){
        int u, v; cin>>u>>v;
        ed.pb({u, v});
    }
    
    while (q--){
        int d; cin>>d;
        int m = n + d;
        vector<int> g[m + 1], a(d + 1);
        for (auto [u, v]: ed){
            g[u].pb(v);
            g[v].pb(u);
        }
        for (int i = 1; i <= d; i++){
            cin>>a[i];
            g[a[i]].pb(n + i);
            g[n + i].pb(a[i]);
        }
        
        int lf = 0;
        for (int i = 1; i <= m; i++){
            lf += (g[i].size() == 1);
        }
        
        if (lf % 2){
            cout<<-1<<"\n";
            continue;
        }
        
        vector<int> f(m + 1);
        function<void(int, int)> dfs = [&](int v, int pr){
            if ((g[v].size() + !pr) == 1){
                f[v] = 1;
                return;
            }
            for (int i: g[v]){
                if (i == pr) continue;
                dfs(i, v);
                f[v] ^= f[i];
            }
        };
        dfs(1, 0);
        
        int out = 0;
        for (int i = 2; i <= m; i++){
            out += (f[i]) ? 1 : 2;
        }
        cout<<out<<"\n";
    }
}

• 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