Submission #1259928

#TimeUsernameProblemLanguageResultExecution timeMemory
1259928abdelhakimSpring cleaning (CEOI20_cleaning)C++20
34 / 100
1096 ms27392 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; } ll solve(vector<vector<ll>>& adj, ll node, ll par, ll& ans,vector<pair<ll,ll>>& parr) { if(node!=par && adj[node].size()==1) { parr[node]={par,1}; if(node!=0) { if(parr[node].second==0) ans+=2; else ans++; } return 1; } ll sm=0; for (auto &&e : adj[node]) { if(e==par)continue; ll val=solve(adj,e,node,ans,parr); sm+=val; } if(adj[node].size()==1 && node==0) sm++; if(node==0 && sm%2) ans=-1; parr[node]={par,sm%2}; if(node!=0) { if(parr[node].second==0) ans+=2; else ans++; } return sm; } int main() { cin.tie(0); ios_base::sync_with_stdio(false); ll n, q; cin>>n>>q; 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); } while(q--) { ll cur=n; ll d; cin>>d; vector<vector<ll>> newadj=adj; for (int i=0;i<d;i++) { ll nd; cin>>nd; nd--; newadj[nd].push_back(cur++); newadj.push_back({nd}); } vector<pair<ll,ll>> parr(n+d); ll ans=0; solve(newadj,0,0,ans,parr); cout<<ans<<endl; } } // #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) // { // parr[node]={par,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; // } // if(adj[node].size()==1 && node==0) sm++; // parr[node]={par,sm%2}; // 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() // { // 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...