Submission #1215290

#TimeUsernameProblemLanguageResultExecution timeMemory
1215290KindaGoodGamesSpring cleaning (CEOI20_cleaning)C++17
34 / 100
1094 ms15688 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define tiii tuple<int,int,int> using namespace std; int n; vector<vector<int>> adj; void DFS(int v, int p, vector<int>& dp, vector<vector<int>>& adj, vector<int>& arr){ dp[v] = arr[v]; if(adj[v].size() == 1 && arr[v] == 0){ dp[v]++; } for(auto u : adj[v]){ if(u == p) continue; DFS(u,v,dp,adj,arr); dp[v] += dp[u]; } } int solve(vector<vector<int>>& adj, int d){ vector<int> arr(n); for(int i = 0; i < d; i++){ int a; cin >> a; a--; arr[a]++; } int r = 0; for(int i = 0; i < n; i++){ if(adj[i].size() > 1){ r = i; break; } } vector<int> dp(n); DFS(r,r,dp,adj, arr); if(dp[r] % 2 == 1){ return -1; } int cnt = 0; for(int i = 0; i < n; i++){ if(dp[i] % 2 == 0){ cnt++; } } return n + d + cnt - 2; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int q; cin >> n>> q; vector<vector<int>> adj(n); for(int i = 0; i < n-1; i++){ int a,b; cin >> a >> b; a--;b--; adj[a].push_back(b); adj[b].push_back(a); } while(q--){ int d; cin >> d; cout << solve(adj, d) << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...