Submission #1259942

#TimeUsernameProblemLanguageResultExecution timeMemory
1259942abdelhakimSpring cleaning (CEOI20_cleaning)C++20
0 / 100
1093 ms10108 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}; cout << "moo " << node << ' ' << parr[node].second << endl; 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++; } cout << "moo " << node << ' ' << parr[node].second << endl; return sm; } void tl3(ll node, vector<pair<ll,ll>>& parr, 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; 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; vector<pair<ll,ll>> parr(n); solve(adj,0,0,old,parr); while(q--) { ll d; cin>>d; vector<ll> v; vector<ll> arr(n); ll ans=old; for (int i=0;i<d;i++) { ll nd; cin>>nd; nd--; if(adj[nd].size()!=1 || arr[nd]){v.push_back(nd);tl3(nd,parr,ans);} arr[nd]++; ans++; } ll val=0; for (int i=0;i<n;i++) { if(adj[i].size()==1) val+=max(arr[i],1LL); else val+=arr[i]; } if(val%2) cout << -1 << endl; else cout << ans << endl; for (auto &&e : v) { tl3(e,parr,ans); } } } // #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...