Submission #931705

#TimeUsernameProblemLanguageResultExecution timeMemory
931705sysiaSpring cleaning (CEOI20_cleaning)C++17
100 / 100
195 ms29640 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; struct Tree{ vector<int>tab, lazy; int size = 1; Tree(int n){ while (size < n) size*=2; tab.assign(2*size, 0); lazy.assign(2*size, 0); } //xor na przedziale suma na przedziale void push(int x, int lx, int rx){ if (!lazy[x]) return; for (auto k: {2*x, 2*x+1}){ tab[k] = (rx-lx+1)/2 - tab[k]; lazy[k] ^= 1; } lazy[x] = 0; }; void update(int x, int lx, int rx, int l, int r){ if (lx > r || rx < l) return; if (lx >= l && rx <= r) { tab[x] = rx-lx+1-tab[x]; lazy[x] ^= 1; return; } int m = (lx+rx)/2; push(x, lx, rx); update(2*x, lx, m, l, r); update(2*x+1, m+1, rx, l, r); tab[x] = tab[2*x] + tab[2*x+1]; } int query(int x, int lx, int rx, int l, int r){ if (lx > r || rx < l) return 0ll; if (lx >= l && rx <= r) return tab[x]; push(x, lx, rx); int m = (lx+rx)/2; return query(2*x, lx, m, l, r) + query(2*x+1, m+1, rx, l, r); } }; void solve(){ int n, q; cin >> n >> q; vector<vector<int>>g(n+1); for (int i = 1; i<n; i++){ int a, b; cin >> a >> b; g[a].emplace_back(b); g[b].emplace_back(a); } vector<int>ord, sz(n+1, 1); function<void(int, int)>subsize = [&](int v, int pa){ for (auto x: g[v]){ if (x == pa) continue; subsize(x, v); sz[v] += sz[x]; } }; subsize(1, 1); debug(sz); vector<int>pos(n+1), head(n+1), par(n+1); function<void(int, int, int)>dfs = [&](int v, int pa, int h){ pos[v] = (int)ord.size(); par[v] = pa; head[v] = h; ord.emplace_back(v); int big = -1; for (auto x: g[v]){ if (x == pa) continue; if (big == -1 || sz[x] > sz[big]) big = x; } if (big != -1) dfs(big, v, h); for (auto x: g[v]){ if (x == pa || x == big) continue; dfs(x, v, x); } }; dfs(1, 0, 1); debug(ord); debug(head); Tree t(n+2); vector<bool>leaf(n+1); int l = 0; auto add = [&](int v){ while (v){ int ll = max(1ll, pos[head[v]]); if (ll <= pos[v]) { t.update(1, 0, t.size-1, ll, pos[v]); debug(v, ll, pos[v]); } v = par[head[v]]; } }; for (int i = 1; i<=n; i++) { leaf[i] = ((int)g[i].size() == 1); if (leaf[i]) { l++; add(i); } } vector<int>ile(n+1); auto solve = [&](vector<int>vt){ int d = (int)vt.size(); int curr = l; auto fix = [&](){ for (auto x: vt) leaf[x] = ((int)g[x].size() == 1); for (auto x: vt){ if (ile[x]&1) add(x); ile[x] = 0; } }; for (auto x: vt){ if (leaf[x]) { leaf[x] = 0; } else { curr++; ile[x]++; add(x); } } if (curr&1) { cout << "-1\n"; fix(); return; } debug(t.query(1, 0, t.size-1, 0, n)); cout << n-1+d+n-1-t.query(1, 0, t.size-1, 1, n-1) << "\n"; fix(); }; while (q--){ int d; cin >> d; vector<int>vt(d); for (auto &x: vt) cin >> x; solve(vt); } } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); 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...