Submission #956284

#TimeUsernameProblemLanguageResultExecution timeMemory
956284thangdz2k7Spring cleaning (CEOI20_cleaning)C++17
35 / 100
157 ms49332 KiB
// author : HuuHung // 25.3.2024 #include <bits/stdc++.h> #define ii pair <int, int> #define F first #define S second #define ll long long #define lb long double #define pb push_back #define vi vector <int> #define vll vector <ll> #define Bit(x, i) ((x) >> (i) & 1) #define Mask(i) (1ll << (i)) #define All(v) (v).begin(), (v).end() using namespace std; void maxzi(int &a, int b){ a = max(a, b); } void minzi(int &a, int b){ a = min(a, b); } const int N = 2e5 + 5; const int mod = 1e9 + 7; const int LG = 20; void add(int &a, int b){ a += b; if (a >= mod) a -= mod; if (a < 0) a += mod; } int Pow(int a, int b){ if (b == 0) return 1; if (b % 2) return 1ll * a * Pow(a, b - 1) % mod; int c = Pow(a, b / 2); return 1ll * c * c % mod; } // * end struct LCA{ vi st, ed, _lg, high, type, num[2]; vector <vi> euler, adj; int cnt, ans, root, leaf; void dfs1(int u, int pa){ ++ cnt; st[u] = cnt; euler[cnt].pb(u); if (adj[u].size() == 1) type[u] = 1, leaf ++; for (int v : adj[u]){ if (v == pa) continue; high[v] = high[u] + 1; dfs1(v, u); euler[++ cnt].pb(u); type[u] ^= type[v]; } ed[u] = cnt; } int check(int u, int v) { return st[u] <= st[v] && ed[v] <= ed[u]; } int min_by_time(int u, int v) { return (st[u] < st[v] ? u : v); } void added(int u, int v){ adj[u].pb(v); adj[v].pb(u); } void resize(int n){ leaf = 0; ans = n - 1; st.resize(n + 3, 0); ed.resize(n + 3, 0); euler.resize(2 * n + 5); high.resize(n + 3, 0); type.resize(n + 3, 0); num[0].resize(n + 3, 0); num[1].resize(n + 3, 0); adj.resize(n + 3); _lg.resize(2 * n + 5); for (int i = 0; i <= 2 * n; ++ i) _lg[i] = log2(i); } void dfs2(int u, int pa){ for (int v : adj[u]){ if (v == pa) continue; num[0][v] = num[0][u]; num[1][v] = num[1][u]; num[type[v]][v] ++; ans += (type[v] ^ 1); dfs2(v, u); } } void init(int r){ root = r; cnt = 0; high[r] = 1; dfs1(r, 0); for (int lg = 1; lg < 20; ++lg) { for (int i = 1; i + (1 << lg) - 1 <= cnt; ++i) euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1])); } dfs2(r, 0); } int get(int u, int v) { int L = min(st[u], st[v]); int R = max(ed[u], ed[v]); int lg = _lg[R - L + 1]; return min_by_time(euler[L][lg], euler[R - (1 << lg) + 1][lg]); } int dist(int t, int u, int pa){ return num[t][u] - num[t][pa]; } } tree; int deg[N], num[N]; vector <int> s; vector <int> nw[N]; int process(){ int ans = tree.ans; sort(s.begin(), s.end(), [&](int u, int v){ return tree.st[u] < tree.st[v]; }); int m = s.size(); for (int i = 1; i < m; ++ i) s.push_back(tree.get(s[i], s[i - 1])); s.pb(tree.root); sort(s.begin(), s.end(), [&](int u, int v) { return tree.st[u] < tree.st[v]; }); s.erase(unique(s.begin(), s.end()), s.end()); reverse(s.begin(), s.end()); vector <int> stk; for (auto u : s){ while (stk.size() && tree.check(u, stk.back())) { int v = stk.back(); stk.pop_back(); nw[u].push_back(v); } stk.push_back(u); } function <void (int, int)> dfs = [&](int u, int pa){ for (int v : nw[u]){ if (v == pa) continue; dfs(v, u); num[u] ^= num[v]; } if (num[u]) ans += (-tree.dist(0, u, pa) + tree.dist(1, u, pa)); }; dfs(tree.root, tree.root); for (int u : s) nw[u].clear(); return ans; } void solve(){ int n, q; cin >> n >> q; tree.resize(n); int root = 1; for (int i = 1, u, v; i < n; ++ i){ cin >> u >> v; tree.added(u, v); deg[u] ++; deg[v] ++; if (deg[u] > 1) root = u; if (deg[v] > 1) root = v; } tree.init(root); while (q --){ for (int v : s) num[v] = 0; s.clear(); vector <int> cur; int d; cin >> d; for (int i = 1; i <= d; ++ i){ int a; cin >> a; if (!num[a]) cur.pb(a); num[a] ++; } int no = 0; for (int v : cur){ num[v] %= 2; if ((num[v] && deg[v] > 1) || (!num[v] && deg[v] == 1)) num[v] = 1, s.pb(v); if (deg[v] == 1) no ++; } //cout << no << endl; if ((tree.leaf - no + d) % 2) cout << -1 << '\n'; else cout << process() + d << '\n'; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; while (t --) solve(); return 0; }

Compilation message (stderr)

cleaning.cpp: In member function 'void LCA::init(int)':
cleaning.cpp:113:78: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  113 |                 euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
      |                                                                           ~~~^~~
#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...