Submission #1245631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245631		mountainsalt	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1096 ms	25156 KiB

cleaning

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int mod=1e9+7;
const int N=2e5+5;

int n,q,ans;
bool leaf[N];
vector<vector<int>> adja(N), adj(N);

int dfs2(int u,int p){
    int leav=leaf[u];
    for(auto v:adj[u]){
        if(v==p) continue;
        int x=dfs2(v,u);
        ans+=2-(x%2);
        leav+=x;
    }
    return leav;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        adja[u].emplace_back(v);
        adja[v].emplace_back(u);
    }
    int __=1;
    while(__++<=q){
        int d;
        cin >> d;
        ans=0;
        adj=adja;
        int id=n;
        for(int i=0; i<d; i++){
            int u;
            cin >> u;
            adj[u].emplace_back(++id);
            adj[id].emplace_back(u);
        }
        int rt=1;
        for(int i=id; i>=1; i--){
            if(adj[i].size()==1) leaf[i]=true;
            else rt=i,leaf[i]=false;
        }
        int error=dfs2(rt,rt);
        if(error%2) cout << -1 << "\n";
        else cout << ans << "\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