Submission #1182123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182123		ByeWorld	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	344 ms	25668 KiB

cleaning

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
// #define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 1e5+10;
const int MAXA = 2e5;
const int INF = 2e9+100;
const int SQRT = 500;
const int LOG = 24;
const int MOD = 1e9;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, q, val[MAXN];
vector<int> adj[MAXN], tree[MAXN];
int root[MAXN], dep[MAXN], sub[MAXN], par[MAXN], sta;

void bd(int nw, int pa){
	par[nw] = pa;
	dep[nw] = dep[pa]+1; sub[nw] = 1;
	for(auto nx : adj[nw]){
		if(nx==pa) continue;
		bd(nx,nw);
		tree[nw].pb(nx);
		sub[nw] += sub[nx]; 
	}
}

int tim, in[MAXN];
void ch(int nw, int ROOT){
	in[nw] = ++tim;
	root[nw] = ROOT;
	if(tree[nw].size()==0) return;

	ch(tree[nw][0], ROOT);
	for(int i=1; i<tree[nw].size(); i++)
		ch(tree[nw][i], tree[nw][i]);
}
struct seg {
	int one[4*MAXN], zer[4*MAXN], laz[4*MAXN];
	void mrg(int id){
		one[id] = one[lf]+one[rg]; zer[id] = zer[lf]+zer[rg];
	}
	void bd(int id, int l, int r){
		if(l==r){
			zer[id] = 1; one[id] = 0; return;
		}
		bd(lf,l,md); bd(rg,md+1,r);
		mrg(id);
	}
	void bnc(int id, int l, int r){
		laz[id] %= 2;
		if(laz[id]==0) return;
		swap(one[lf], zer[lf]); laz[lf] += laz[id];
		swap(one[rg], zer[rg]); laz[rg] += laz[id];
		laz[id] = 0;
	}
	pii que(int id,int l,int r,int x,int y){
		if(x<=l && r<=y) return {one[id], zer[id]};
		if(r<x || y<l) return {0, 0};
		bnc(id,l,r);
		pii le = que(lf,l,md,x,y), ri = que(rg,md+1,r,x,y);
		return {le.fi+ri.fi, le.se+ri.se};
	}
	void upd(int id,int l,int r,int x,int y,int p){
		if(x<=l && r<=y){
			laz[id] += p;
			if(p==1 || p==-1){
				swap(one[id], zer[id]);
			}
			return; 
		}
		if(r<x || y<l) return;
		bnc(id,l,r);
		upd(lf,l,md,x,y,p); upd(rg,md+1,r,x,y,p);
		mrg(id);
	}
} A;
int lg = 0;
void UP(int nw, int val){
	lg++;
	if(lg >= 20) assert(false);
	if(root[nw]==sta){
		int roo = root[nw];
		A.upd(1,1,n,in[roo],in[nw], val);
		return;
	}
	int roo = root[nw];
	A.upd(1,1,n,in[roo],in[nw], val);
	nw = par[roo];
	UP(nw, val);
}

void UPD(int nw, int val){
	lg = 0;
	UP(nw, val);
}
bool isleaf[MAXN];
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1; i<=n-1; i++){
		int u, v; cin>>u>>v;
		adj[u].pb(v); adj[v].pb(u);
	}
	for(int i=1; i<=n; i++)
		if(adj[i].size() != 1) sta = i;
	bd(sta,0);
	for(int i=1; i<=n; i++){
		if(tree[i].size()==0) continue;
		for(int j=1; j<tree[i].size(); j++)
			if(sub[tree[i][0]] < sub[tree[i][j]])
				swap(tree[i][0], tree[i][j]);
	}
	ch(sta,sta);

	A.bd(1,1,n);
	for(int i=1; i<=n; i++){
		if(tree[i].size() == 0){
			isleaf[i] = 1;
			// cout << i << " updi\n";
			UPD(i, 1);
		}
	}
	// for(int i=1; i<=n; i++){
	// 	pii ret = A.que(1,1,n,in[i],in[i]);
	// 	// cout << ret.fi << ' ' << ret.se << " reet\n";
	// }

	while(q--){
		int num; cin>>num; vector<int>add;
		vector <int> bacleaf;
		for(int i=1; i<=num; i++){
			int x; cin>>x; add.pb(x);
			if(isleaf[x]){ // pop
				UPD(x, 1);
				isleaf[x] = 0; bacleaf.pb(x);
			}
			UPD(x, 1);
		}
		if(A.que(1,1,n,in[sta],in[sta]).fi) cout << "-1\n";
		else {
			int ans = num;
			pii ret = A.que(1,1,n,1,n);
			// cout << ret.fi << ' ' << ret.se << " ret\n";
			ans += ret.fi + 2*ret.se;
			cout << ans-2 << '\n';
		}

		for(int i=0; i<add.size(); i++){
			UPD(add[i], 1);
		}
		for(auto in : bacleaf){
			isleaf[in] = 1;
			UPD(in, 1);
		}
	}
}

• 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