Submission #1173133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173133		Dan4Life	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	235 ms	23136 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
const int mxN = (int)1e5+10;

int sub[mxN], st[mxN], head[mxN], p[mxN], ind[mxN], chainsz[mxN];
int n, q, dfs_tim, par, root, tot;
map<int,int> cnt;
vi adj[mxN];

struct LazySegTree{
	vi seg, lz;
	int L, R;
	LazySegTree(int l, int r){
		L=l,R=r; int sz = r-l+1;
		seg.clear(); seg.shrink_to_fit();
		lz.clear(); seg.shrink_to_fit();
		seg.resize(sz*2,0); lz.resize(sz*2,0);
	}
	
	void prop(int p, int l, int r){
		if(l==r or !lz[p]) return;
		int mid = (l+r)/2; int rp = p+2*(mid-l+1);
		apply(p+1,l,mid); apply(rp,mid+1,r); lz[p] = 0;
	}
	
	void apply(int p, int l, int r){
		seg[p]=(r-l+1)-seg[p]; lz[p]=1-lz[p];
	}
	
	void upd(int i, int j, int v, int p, int l, int r){
		if(i>r or j<l or i>j) return; prop(p,l,r);
		if(i<=l and r<=j){ apply(p,l,r); return; }
		int mid = (l+r)/2; int rp = p+2*(mid-l+1);
		upd(i,j,v,p+1,l,mid), upd(i,j,v,rp,mid+1,r);
		seg[p] = seg[p+1]+seg[rp];
	}
	
	int query(int i, int j, int p, int l, int r){
		if(i>r or j<l or i>j) return 0; prop(p,l,r);
		if(i<=l and r<=j) return seg[p];
		int mid = (l+r)/2; int rp = p+2*(mid-l+1);
		return query(i,j,p+1,l,mid)+query(i,j,rp,mid+1,r);
	}
	void upd(int i, int j, int v){ upd(i,j,v,0,L,R); }
	int query(int i=-1, int j=-1){
		if(i==-1) return query(L,R,0,L,R); 
		return query(i,j,0,L,R);
	}
};
vector<LazySegTree> seg;

bool dfs2(int s, int p){
	bool leafs = 0;
	for(auto u : adj[s]){
		if(u==p) continue;
		leafs^=dfs2(u,s);
	}
	if(sz(adj[s])==1) leafs^=1;
	if(!leafs) seg[ind[head[s]]].upd(st[s],st[s],1),tot++;
	return leafs;
}

void dfs(int s, int p){
	sub[s] = 1;
	for(auto &u : adj[s]){
		if(u==p) continue;
		int x = adj[s][0];
		dfs(u,s); sub[s]+=sub[u];
		if(x==p or sub[u]>sub[x]) swap(adj[s][0],u);
	}
}

void dfsHld(int s, int par, int h){
	st[s] = dfs_tim++; p[s] = par; 
	head[s] = h; chainsz[h]++;
	for(auto u : adj[s]){
		if(u==par) continue;
		dfsHld(u,s,u==adj[s][0]?h:u);
	}
}

void upd(int x){
	while(x){
		tot-=seg[ind[head[x]]].query(st[head[x]],st[x]);
		seg[ind[head[x]]].upd(st[head[x]],st[x],1);
		tot+=seg[ind[head[x]]].query(st[head[x]],st[x]);
		x = p[head[x]];
	}
}

int main(){
	cin >> n >> q;
	for(int i = 0; i < n-1; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = 1; i <= n; i++) if(sz(adj[i])>1) root=i;
	dfs(root,0); dfsHld(root,0,root); 
	for(int i = 1; i <= n; i++){
		if(head[i]!=i) continue;
		seg.pb(LazySegTree(st[i],st[i]+chainsz[i]-1));
		ind[i] = sz(seg)-1;
	}
	dfs2(root,0);
	while(q--){
		int d, x; cin >> d; cnt.clear();
		for(int i = 0; i < d; i++) cin >> x, cnt[x]++;
		for(auto [u,v] : cnt) if((v^(sz(adj[u])==1))%2) upd(u);
		bool rt = seg[ind[root]].query(st[root],st[root]);
		if(!rt) cout << -1 << "\n";
		else cout << n-1+d+tot-rt << "\n";
		for(auto [u,v] : cnt) if((v^(sz(adj[u])==1))%2) upd(u);
	}
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30