제출 #1166984

#제출 시각아이디문제언어결과실행 시간메모리
1166984dragstSpring cleaning (CEOI20_cleaning)C++20
100 / 100
220 ms24644 KiB
#include <bits/stdc++.h> using namespace std; long long m=1, k=1, p[100005], h[100005], st[400005], lazy[400005], dp[100005], tour[100005]; long long sz[100005], nxt[100005], head[100005], chain[100005], pos[100005], check[100005]; vector<long long> adj[100005], vv; void dfs(long long x) { sz[x]=1; for (auto y: adj[x]) { if (y!=p[x]) { h[y]=h[x]+1; p[y]=x; dfs(y); sz[x]+=sz[y]; if (sz[y]>sz[nxt[x]]) {nxt[x]=y;}; dp[x]+=dp[y]; dp[x]%=2; if (dp[x]==0) {dp[x]=2;}; }; }; if (x>1 && adj[x].size()==1) {dp[x]=1;}; } void hld(long long x) { if (head[m]==0) {head[m]=x;}; chain[x]=m; tour[k]=x; pos[x]=k; k++; if (nxt[x]>0) {hld(nxt[x]);}; for (auto y: adj[x]) { if (y!=p[x] && y!=nxt[x]) { m++; hld(y); }; }; } void build(long long x, long long l, long long r) { if (l>r) {return;} else if (l==r) {st[x]=dp[tour[l]];} else { build(x*2, l, (l+r)/2); build(x*2+1, (l+r)/2+1, r); st[x]=st[x*2]+st[x*2+1]; }; } void fix(long long x, long long l, long long r) { if (lazy[x]%2==1) { st[x]=3*(r-l+1)-st[x]; if (l<r) {lazy[x*2]+=lazy[x]; lazy[x*2+1]+=lazy[x];}; lazy[x]=0; }; } void update(long long x, long long l, long long r, long long pos1, long long pos2) { if (l<=r) {fix(x, l, r);}; if (l>r || l>pos2 || r<pos1) {return;} else if (pos1<=l && r<=pos2) {lazy[x]++; fix(x, l, r);} else { update(x*2, l, (l+r)/2, pos1, pos2); update(x*2+1, (l+r)/2+1, r, pos1, pos2); st[x]=st[x*2]+st[x*2+1]; }; } long long get(long long x, long long l, long long r, long long pos1, long long pos2) { if (l>r || l>pos2 || r<pos1) {return 0LL;} else if (pos1<=l && r<=pos2) {fix(x, l, r); return st[x];} else {fix(x, l, r); return get(x*2, l, (l+r)/2, pos1, pos2)+get(x*2+1, (l+r)/2+1, r, pos1, pos2);}; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); long long n, q, i, u, v; cin >> n >> q; for (i=1; i<n; i++) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }; dfs(1); hld(1); build(1, 1, n); while (q--) { cin >> i; while (i--) { cin >> u; vv.push_back(u); check[u]++; if (u>1 && adj[u].size()==1 && check[u]==1) {continue;}; while (u>0) { update(1, 1, n, pos[head[chain[u]]], pos[u]); u=p[head[chain[u]]]; }; }; v=get(1, 1, n, pos[1], pos[1]); if (adj[1].size()==1 && check[1]==0 && v==2) {cout << -1 << "\n";} else if ((adj[1].size()>1 || check[1]) && v==1) {cout << -1 << "\n";} else {cout << get(1, 1, n, 2, n)+vv.size() << "\n";}; while (!vv.empty()) { u=vv.back(); vv.pop_back(); check[u]--; if (u>1 && adj[u].size()==1 && check[u]==0) {continue;}; while (u>0) { update(1, 1, n, pos[head[chain[u]]], pos[u]); u=p[head[chain[u]]]; }; }; }; }
#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...