Submission #404937

#TimeUsernameProblemLanguageResultExecution timeMemory
404937silverfishSpring cleaning (CEOI20_cleaning)C++14
19 / 100
1098 ms13772 KiB
#include <bits/stdc++.h> using namespace std; /*<DEBUG>*/ #define tem template <typename #define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i) #define _op debug& operator<< tem C > auto test(C *x) -> decltype(cerr << *x, 0LL); tem C > char test(...); tem C > struct itr{C begin, end; }; tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; } struct debug{ #ifdef _LOCAL ~debug(){ cerr << endl; } tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; } tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); } tem T, typename U > _op (pair<T, U> i){ return *this << "< " << i.first << " , " << i.second << " >"; } tem T> _op (itr<T> i){ *this << "{ "; for(auto it = i.begin; it != i.end; it++){ *this << " , " + (it==i.begin?2:0) << *it; } return *this << " }"; } #else tem T> _op (const T&) { return *this; } #endif }; tem T> string _ARR_(T* arr, int sz){ string ret = "{ " + to_string(arr[0]); for(int i = 1; i < sz; i++) ret += " , " + to_string(arr[i]); ret += " }"; return ret; } #define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]" /*</DEBUG>*/ typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef unsigned int uint; typedef pair<int, int> pii; //mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb push_back #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define TC int __TC__; cin >> __TC__; while(__TC__--) #define ar array const int INF = 1e9 + 7, N = 2e5 + 10; vector<int> adj[N]; int win[N], wout[N], in[N], out[N], add[N]; int ans = 0, n, q, d, cur,fst=0, leafs = 0, par[N], nin, nout; bool was_leaf[N], leaf[N]; void dfs(int u, int p=fst){ par[u] = p; for(int v : adj[u]){ if(v != p){ dfs(v, u); in[u] += out[v]; } } if(adj[u].size() == 1){ in[u] = 0; out[u] = 1; ++leafs; leaf[u] = 1; }else{ out[u] = (in[u]%2 ? 1 : 2); } ans += in[u]; win[u] = in[u]; wout[u] = out[u]; return; } int main() { FAST; cin >> n >> q; for(int i = 0; i < n-1; ++i){ int u, v; cin >> u >> v; --u; --v; adj[u].pb(v); adj[v].pb(u); } for(int i = 0; i < n; ++i){ if(adj[fst].size() == 1 && adj[i].size() != 1) fst = i; } dfs(fst); debug() << exp(ans); while(q--){ cur = n-1; cin >> d; for(int i = 0; i < d; ++i){ ++cur; cin >> add[i]; --add[i]; if(leaf[add[i]]){ was_leaf[i] = 1; leaf[add[i]] = 0; --leafs; } ++leafs; adj[add[i]].pb(cur); in[cur] = 0; out[cur] = 1; int u = add[i]; while(1){ ans -= in[u]; in[u] = out[u] = 0; for(int v : adj[u]){ if(v != par[u]){ in[u] += out[v]; } } out[u] = (in[u]%2 ? 1 : 2); ans += in[u]; if(u == fst) break; u = par[u]; } } debug() << exp(ans); cout << (leafs%2 ? -1 : ans) << '\n'; for(int i = 0; i < d; ++i){ adj[add[i]].pop_back(); if(was_leaf[i]){ leafs++; leaf[add[i]] = 1; was_leaf[i] = 0; } leafs--; int u = add[i]; while(1){ ans += win[u] - in[u]; in[u] = win[u]; out[u] = wout[u]; if(u == fst) break; u = par[u]; } } debug() << exp(ans); } 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...