Submission #1173127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173127		Dan4Life	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	239 ms	18932 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];
int n, q, dfs_tim, par, root;
map<int,int> cnt;
vi adj[mxN];

template<int SZ> struct LazySegTree{
	bitset<SZ*2> lz;
	int seg[SZ*2];
	
	void init(){
		lz.reset();
		for(int i = 0; i < SZ*2; i++) seg[i] = 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=0, int l=0, int r=n-1){
		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=0, int l=0, int r=n-1){
		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);
	}
};

LazySegTree<mxN> 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.upd(st[s],st[s],1);
	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;
	for(auto u : adj[s]){
		if(u==par) continue;
		dfsHld(u,s,u==adj[s][0]?h:u);
	}
}

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

int main(){
	cin >> n >> q; seg.init();
	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); 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);
		if(!seg.query(0,0)) cout << -1 << "\n";
		else cout << n-1+d+seg.query(1,n-1) << "\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