Submission #1259874

#TimeUsernameProblemLanguageResultExecution timeMemory
1259874abdelhakimSpring cleaning (CEOI20_cleaning)C++20
0 / 100
1096 ms15968 KiB
#include <bits/stdc++.h> #define ll long long #define dbg(x) cerr << #x << ' ' << x << endl; #define inf 1e18 using namespace std; void printvec(vector<ll>& vec) { for (auto &&e : vec) { cout << e << ' '; } cout << endl; } vector<pair<ll,ll>> parr; ll solve(vector<vector<ll>>& adj, ll node, ll par, ll& ans) { if(node!=par && adj[node].size()==1) { return 1; } ll sm=0; for (auto &&e : adj[node]) { if(e==par)continue; ll val=solve(adj,e,node,ans); sm+=val; if(val%2)ans++; else ans+=2; } parr[node]={par,sm%2}; if(adj[node].size()==1 && node==0) sm++; if(node==0 && sm%2) ans=-1; return sm; } void climb(ll node, ll& ans) { while(node!=0) { if(parr[node].second==0) { ans--; } else ans++; parr[node].second^=1; node=parr[node].first; } } int main() { cin.tie(0); ios_base::sync_with_stdio(false); ll n, q; cin>>n>>q; parr.resize(n); vector<vector<ll>> adj(n); for (int i=0;i<n-1;i++) { ll u, v; cin>>u>>v; u--;v--; adj[u].push_back(v); adj[v].push_back(u); } ll old=0; solve(adj,0,0,old); while(q--) { ll d; cin>>d; vector<ll> v; vector<ll> v2(n); ll ans=old; for (int i=0;i<d;i++) { ll nd; cin>>nd; nd--; v.push_back(nd); v2[nd]++; climb(nd,ans); } ll val=0; for (int i=0;i<n;i++) { if(adj[i].size()==1)val+=max(1LL,v2[i]); else val+=v2[i]; } if(val%2) cout << -1 << endl; else cout << ans+d << endl; for (auto &&nd : v) { climb(nd,ans); } } }
#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...