Submission #969935

#TimeUsernameProblemLanguageResultExecution timeMemory
969935shadow_samiSpring cleaning (CEOI20_cleaning)C++17
0 / 100
1014 ms18676 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<ll,ll> pi; typedef vector<ll> vi; #define ff first #define ss second #define fip(a,b) for(ll i = a ; i<b;i++) #define fjp(a,b) for(ll j = a ; j<b;j++) #define fp(k,a,b) for(ll k = a ; k<b;k++) #define fin(a,b) for(ll i = a;i>=b;i--) #define fjn(a,b) for(ll j = a;j>=b;j--) #define fn(k,a,b) for(ll k = a;k>=b;k--) #define fx(k) for(auto x : k) #define ordered_set <ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> #define totalone(x) _builtin_popcountll(x) #define frontzero(x) _builtin_clzll(x) #define backzero(x) _builtin_ctzll(x) #define nli "\n"; #ifndef ONLINE_JUDGE #define debug(x) cerr<<#x<<" ";printn(x);cerr<<nli; #else #define debug(x) #endif void printn(ll x){cerr<<x<<" ";}; void printn(int x){cerr<<x<<" ";}; void printn(double x){cerr<<x<<" ";}; void printn(bool x){cerr<<x<<" ";}; void printn(char x){cerr<<x<<" ";}; void printn(string x){cerr<<x<<" ";}; template<class T> void printn(set<T> s); template<class T> void printn(vector<T> s); template<class T,class V> void printn(pair<T, V> s); template<class T,class V> void printn(map<T, V> s); template<class T> void printn(set<T> s){cerr<<"{ ";fx(s){printn(x);cerr<<",";};cerr<<"}";} template<class T> void printn(vector<T> s){cerr<<"[ ";fx(s){printn(x);cerr<<",";};cerr<<"]";} // template<class T> void printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ printn(xx);cerr<<" "; } cerr<<"]"; }; template<class T,class V> void print(pair<T,V> s){cerr<<"( ";print(s.ff);cerr<<",";print(s.ss);cerr<<")";} template<class T,class V> void print(map<T,V> s){cerr<<"[ ";fx(s){print(x);cerr<<",";};cerr<<"]";} const ll mx = 1e5 + 5; const ll mod = 1e9 + 7; ll n,m,sum,ans,res,cnt,tp,tp2,tptp; ll sr,de; ll tnc[mx]; vi adj[mx]; vi adj2[mx]; bool mark[mx]; ll dfs(ll u,ll par){ ll pt = 0; fx(adj[u]) if(x!=par){ pt += dfs(x,u); } fx(adj2[u]) if(x!=par){ pt += dfs(x,u); } if(par!=-1 && (ll)adj[u].size()+(ll)adj2[u].size()==1) pt = 1; if(!(pt&1)) mark[u] = 1,cnt++; return pt; } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // freopen("input1.txt","r",stdin); // freopen("output1.txt","w",stdout); // freopen("error1.txt","w",stderr); cin>>n>>m; fip(0,n-1){ cin>>sr>>de; adj[sr].push_back(de); adj[de].push_back(sr); } ans = 0; res = n+1; fip(0,m){ cin>>tp; vi a(tp); for(auto &x: a) cin>>x; fx(a){ adj2[x].push_back(res); adj2[res].push_back(x); res++; } ans = 0; cnt = 0; tp = -1; fip(1,res+1) mark[i] = 0; fip(1,n+1) if(((ll)adj[i].size()+adj2[i].size())>1){ tp = i; break; } dfs(tp,-1); ans = (mark[tp] ? n + tp + cnt - 2 : -1); cout<<ans<<nli; fip(1,res+1) adj2[i].clear(); } cerr<<"time elapsed: "<<setprecision(6)<<1000.0*clock()/CLOCKS_PER_SEC<<"ms"<<nli; return 0; }
#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...