Submission #1039119

#TimeUsernameProblemLanguageResultExecution timeMemory
1039119TonylSpring cleaning (CEOI20_cleaning)C++17
28 / 100
1065 ms10328 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 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; return fr; } void flip(int i, bool rev=false) { while (i != -1) { D(i); if (parent[i] != -1) { if (rev) children[i]--; if (is_leaf[i] && children[i] == 0) { if (!rev) children[i]++; return; } else if (!rtr[i]) total--; else total++; if (!rev) children[i]++; } D(total); rtr[i] = !rtr[i]; i = parent[i]; } } 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); REP(i,n) { if (graph[i].size() > 1) {nonleaf = i; break;} } calc(nonleaf); 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); } int tot = total; bool frb = rtr[nonleaf]; trav(a, added) flip(a, 1); assert(prv == total); 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...