Submission #417048

#TimeUsernameProblemLanguageResultExecution timeMemory
417048ACmachineSpring cleaning (CEOI20_cleaning)C++17
34 / 100
1086 ms42436 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l)) #define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l)) #define REP(i, n) FOR(i, 0, n, 1) #define REPD(i, n) FOR(i, n, 0, 1) #define pb push_back typedef long long ll; struct node{ int even = 0, odd = 0; int flag = 0; void apply(int l, int r, int val){ swap(even, odd); flag ^= 1; } }; struct segtree{ node comb(node const &a, node const &b){ node res; res.even = a.even + b.even; res.odd = a.odd + b.odd; return res; } void push(int l, int r, int v){ if(tree[v].flag == 0) return; tree[v<<1].apply(l, r, tree[v].flag); tree[v<<1|1].apply(l, r, tree[v].flag); tree[v].flag = 0; } vector<node> tree; int n; segtree(){} segtree(int _n){ n = 1; while(n < _n) n*= 2; tree.resize(2 * n); } void build(vector<node> &init){ REP(i, n){ if(i < init.size()){ tree[i + n] = init[i]; } } FORD(i, n - 1, 1, 1){ tree[i] = comb(tree[i << 1], tree[i << 1|1]); } } node query(int l, int r){return query0(l, r, 0, n, 1);} node query0(int l, int r, int beg, int end, int v){ if(beg >= l && end <= r) return tree[v]; push(beg, end, v); int mid = (beg + end) >> 1; node res; if(beg >= r || mid <= l) res = query0(l, r, mid, end, v<<1|1); else if(mid >= r || end <= l) res = query0(l, r, beg, mid, v<<1); else res = comb(query0(l, r, beg, mid, v<<1), query0(l, r, mid, end, v<<1|1)); return res; } void upd(int l, int r, int val){ upd0(l, r, 0, n, 1, val); } void upd0(int l, int r, int beg, int end, int v, int val){ if(beg >= r || end <= l) return; if(beg >= l && end <= r){ tree[v].apply(beg, end, val); return; } push(beg, end, v); int mid = (beg + end) >> 1; upd0(l, r, beg, mid, v<<1, val); upd0(l, r, mid, end, v<<1|1, val); tree[v] = comb(tree[v<<1], tree[v<<1|1]); } }; struct heavy_light{ vector<vector<int>> g; int n; vector<int> pv, sz, in, out, depth, nxt; segtree st; int timer = 0; heavy_light(vector<vector<int>> &_g) : g(_g){ n = g.size(); st = segtree(n); pv.resize(n, -1); sz.resize(n); in.resize(n); out.resize(n); depth.resize(n, 0); nxt.resize(n); function<void(int, int)> dfs_sz = [&](int v, int p){ sz[v] = 1; pv[v] = p; if(p != -1) depth[v] = depth[p] + 1; for(int &x : g[v]){ if(x == p) continue; dfs_sz(x, v); sz[v] += sz[x]; if(sz[x] > sz[g[v][0]]) swap(x, g[v][0]); } }; dfs_sz(0, -1); function<void(int)> dfs_hld = [&](int v){ in[v] = timer++; for(int x : g[v]){ if(x == pv[v]) continue; nxt[x] = (x == g[v][0] ? nxt[v] : x); dfs_hld(x); } out[v] = timer; }; dfs_hld(0); } node query_path(int u, int v){ node ans; for(;nxt[u] != nxt[v]; v = pv[nxt[v]]){ if(depth[nxt[u]] > depth[nxt[v]]) swap(u, v); ans = st.comb(ans, st.query(in[nxt[v]], in[v] + 1)); } if(depth[u] > depth[v]) swap(u, v); ans = st.comb(ans, st.query(in[u], in[v] + 1)); return ans; } void update_path(int u, int v, int val){ for(;nxt[u] != nxt[v]; v = pv[nxt[v]]){ if(depth[nxt[u]] > depth[nxt[v]]) swap(u, v); st.upd(in[nxt[v]], in[v] + 1, val); } if(depth[u] > depth[v])swap(u, v); st.upd(in[u], in[v] + 1, val); } }; const int mx = 200005; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<vector<int>> g(mx); vector<int> queries(q); REP(i, n - 1){ int u, v; cin >> u >> v; u--; v--; g[u].pb(v); g[v].pb(u); } int nn = n; vector<int> ans(q, 0); REP(i, q){ int d; cin >> d; queries[i] = d; REP(j, d){ int a; cin >> a; a--; g[a].pb(nn); g[nn].pb(a); nn++; } } heavy_light hld(g); vector<node> init(nn); REP(i, nn){ init[i].even = 1; } hld.st.build(init); vector<bool> oleaf(nn, false); int num_leaves = 0; REP(i, n){ int cnt = 0; for(int x : g[i]){ if(x < n) cnt++; } if(cnt == 1){ oleaf[i] = true; num_leaves++; hld.update_path(i, 0, 1); } } int curr = n; vector<int> changed; REP(i, q){ changed.clear(); FOR(j, curr, curr + queries[i], 1){ if(oleaf[hld.pv[j]]){ changed.pb(hld.pv[j]); oleaf[hld.pv[j]] = false; hld.update_path(hld.pv[j], 0, 1); } hld.update_path(j, 0, 1); } auto no = hld.st.query(0, nn); auto no2 = hld.st.query(0, 1); no.odd -= no2.odd; no.even -= no2.even; no.even -= (nn - (n + queries[i])); ans[i] = no.even * 2 + no.odd; if((num_leaves - (int)changed.size() + queries[i]) % 2 == 1) ans[i] = -1; FOR(j, curr, curr + queries[i], 1){ hld.update_path(j, 0, 1); } for(int v : changed){ oleaf[v] = true; hld.update_path(v, 0, 1); } curr += queries[i]; } REP(i, q){ cout << ans[i] << "\n"; } return 0; }

Compilation message (stderr)

cleaning.cpp: In member function 'void segtree::build(std::vector<node>&)':
cleaning.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             if(i < init.size()){
      |                ~~^~~~~~~~~~~~~
#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...