Submission #1039170

#TimeUsernameProblemLanguageResultExecution timeMemory
1039170TonylSpring cleaning (CEOI20_cleaning)C++17
100 / 100
121 ms19808 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using pi = pair<int,int>; #define REP(i,n) for (int i = 0; i < n; i++) #define trav(a,x) for (auto &a : x) #define all(x) (x).begin(), (x).end() #define submit(a,b) cout << a << " " << b << endl #define D(x) //cerr << #x << ": " << x << endl; const int MAX_N = 2e5; int n,q; vector<vi> graph; vi children; int total = 0; int nonleaf = 0; bool rtr[MAX_N]; bool is_leaf[MAX_N]; int parent[MAX_N]; int top[MAX_N]; int hv[MAX_N]; int subtr[MAX_N]; int ind[MAX_N]; bool rawr[MAX_N]; int pref[MAX_N]; void dfs1(int i, int par = -1) { int &sub = subtr[i]; sub = 1; trav(nei, graph[i]) { if (nei == par) continue; dfs1(nei, i); sub += subtr[nei]; } } int id = 0; void dfs2(int i, int par = -1, int head = nonleaf) { top[i] = head; ind[i] = id++; int heaviest = -1; int mass = 0; trav(nei, graph[i]) { if (nei == par) continue; if (subtr[nei] > mass) { mass = subtr[nei]; heaviest = nei; } } if (heaviest == -1) return; dfs2(heaviest, i, head); trav(nei, graph[i]) { if (nei == par) continue; if (nei == heaviest) continue; dfs2(nei, i, nei); } } int calc(int i, int par = -1) { if (par == -1) total = 0; parent[i] = par; int fr = 0; trav(nei, graph[i]) { if (nei == par) continue; int o = calc(nei, i); total += o; fr += o; } fr += children[i]; total += children[i]; if (fr == 0) {fr = 1; is_leaf[i] = 1;} if (fr > 2) fr = 2 - (fr%2); rtr[i] = fr == 1; rawr[ind[i]] = fr == 1; return fr; } vector<vi> bots; vi to_check; void flip(int i, bool rev=false) { while (i != -1) { D(i); if (rev) children[i]--; if (is_leaf[i] && children[i] == 0) { if (!rev) children[i]++; return; } if (!rev) children[i]++; if (top[i] == i) { if (i != nonleaf) { if (!rtr[i]) total--; else total++; } rtr[i] = !rtr[i]; i = parent[i]; } else { bots[top[i]].push_back(ind[i]); to_check.push_back(top[i]); i = top[i]; } D(total); } } void exec_heavy() { trav(check, to_check) { D(check); if (bots[check].size() == 0) continue; sort(all(bots[check])); vi bts; trav(bot, bots[check]) { if (bts.size() && bts.back() == bot) bts.pop_back(); else bts.push_back(bot); } bool flp = bts.size()%2; int prev = ind[check]; trav(bot, bts) { D(bot); int ones = pref[bot+1]-pref[prev+1]; int twos = (bot-prev) - ones; D(total); D(ones); D(twos); if (flp) { total += ones; total -= twos; } D(total); prev = bot; flp = !flp; } bots[check] = vi(); } to_check = vi(); } void make_graph() { graph.assign(n, vi()); REP(i,n-1) { int u,v; cin >> u >> v; u--; v--; graph[u].push_back(v); graph[v].push_back(u); } children.assign(n, 0); bots.assign(n, vi()); REP(i,n) { if (graph[i].size() > 1) {nonleaf = i; break;} } dfs1(nonleaf); dfs2(nonleaf); calc(nonleaf); REP(i,n) { pref[i+1] = pref[i] + rawr[i]; } D(total); } int query() { int d; cin >> d; D(d); vi added; int prv = total; REP(dd, d) { int a; cin >> a; a--; added.push_back(a); flip(a); } exec_heavy(); int tot = total; bool frb = rtr[nonleaf]; trav(a, added) flip(a, 1); exec_heavy(); total = prv; if (frb) return -1; else return tot+d; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> q; make_graph(); REP(qq, q) { cout << query() << "\n"; } }
#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...