Submission #701805

#	Time	Username	Problem	Language	Result	Execution time	Memory
701805		GrandTiger1729	Spring cleaning (CEOI20_cleaning)	C++17	34 / 100	1074 ms	20884 KiB

cleaning

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

const int M = 1e5 + 10;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    vector<vector<int>> g(n + M);
    for (int i = 0; i < n - 1; i++){
        int u, v; cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    long long ans = 0;
    vector<bool> vis(n + M);
    function<int(int)> dfs = [&](int u){
        if (u != 0 && g[u].size() == 1) return 1;
        vis[u] = 1;
        int ret = 0;
        for (auto &v: g[u]){
            if (vis[v]) continue;
            int res = dfs(v);
            ret += res;
        }
        ans += ret;
        ret = ret % 2 == 0? 2: 1;
        vis[u] = 0;
        return ret;
    };
    while (q--){
        int m; cin >> m;
        vector<int> a(m);
        for (int i = 0; i < m; i++){
            cin >> a[i];
            a[i]--;
        }
        for (int i = 0; i < m; i++){
            g[a[i]].push_back(n + i);
            g[n + i].push_back(a[i]);
        }
        ans = 0;
        int res = dfs(0);
        // cout << " --- " << res << ' ' << ans << endl;
        if (g[0].size() == 1)
            res--;
        cout << (res == 1? -1: ans) << '\n';
        for (int i = 0; i < m; i++){
            g[a[i]].pop_back();
            g[n + i].pop_back();
        }
    }
    return 0;
}

• 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