Submission #1123881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123881		kikaxe4781	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	250 ms	24628 KiB

cleaning

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define pir pair<int,int>
using namespace std;
const int maxn = 2e5 + 5;

template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}

struct segment_tree{
	int seg[4*maxn];
	bool lazy[4*maxn];
	
	void downlazy(int v,int l,int r){
		if (!lazy[v]) return;
		
		seg[v] = (r - l + 1) - seg[v];
		if (l != r){
			lazy[2*v + 1] ^= 1;
			lazy[2*v + 2] ^= 1;
		}
		lazy[v] = 0;
	}
	
	void update(int l,int r,int v,int lx,int rx,int val){
		downlazy(v,l,r);
		if (l > rx || r < lx) return;
		if (l >= lx && r <= rx){
			lazy[v] ^= val;
			downlazy(v,l,r);
			return;
		}
		
		int w = (l + r)/2;
		update(l,w,2*v + 1,lx,rx,val);
		update(w + 1,r,2*v + 2,lx,rx,val);
		seg[v] = seg[2*v + 1] + seg[2*v + 2];
	}
	
	int calc(int l,int r,int v,int lx,int rx){
		downlazy(v,l,r);
		if (l > rx || r < lx) return 0;
		if (l >= lx && r <= rx) return seg[v];
		
		int w = (l + r)/2;
		return calc(l,w,2*v + 1,lx,rx) + calc(w + 1,r,2*v + 2,lx,rx);
	}
} seg;

vector <int> Q[maxn],vec[maxn];
pir pos[maxn];
int chain[maxn],D[maxn],mx[maxn],father[maxn],deg[maxn];

void input(int n,int q){
	for (int i = 1 ; i < n ; i++){
		int u,v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	
	for (int id = 1 ; id <= q ; id++){
		int len;
		cin >> len;
		Q[id].resize(len);
		
		for (int i = 0 ; i < len ; i++) cin >> Q[id][i];
	}
}

int get_root(int n){
	for (int i = 1 ; i <= n ; i++)
	    if (vec[i].size() >= 2) return i;
	return 1;
}

void dfs(int u,int par){
	mx[u] = D[u];
	
	for (int v : vec[u])   
	    if (v != par){
	    	deg[u]++;
	    	D[v] = D[u] + 1;
	    	father[v] = u;
	    	dfs(v,u);
	    	maxi(mx[u],mx[v]);
		}
}
void HLD_dfs(int u,int par,bool state,int &m){
	pos[u].fi = ++m;
	chain[u] = (state) ? u : chain[par];
	
	int nxt = 0;
	for (int v : vec[u])
	    if (v != par && mx[v] == mx[u]){
	    	nxt = v;
	    	break;
		}
	
	if (nxt > 0) HLD_dfs(nxt,u,0,m);
	for (int v : vec[u])
	    if (v != par && v != nxt)
	       HLD_dfs(v,u,1,m);
	    
	pos[u].se = m;
}

void HLD_update(int u,int n,int val){
	while (D[u] >= 1){
		seg.update(1,n,0,pos[chain[u]].fi,pos[u].fi,val);
		u = father[chain[u]];
	}
}

void prepare(int root,int n){
	D[root] = 1;
	dfs(root,0);
	
	int m = 0;
	HLD_dfs(root,0,1,m);
	
	//prepare leaf
	for (int u = 1 ; u <= n ; u++)
	    if (vec[u].size() == 1)
	       HLD_update(u,n,1);
}

void add_to_tree(int id,int n){
	for (int u : Q[id]){
		deg[u]++;
		
		if (deg[u] > 1)
		   HLD_update(u,n,1); 
	}
}

void clean_up(int id,int n){
	for (int u : Q[id]){
		if (deg[u] > 1)
		   HLD_update(u,n,1);
		
		deg[u]--;
	}
}

int get_answer(int root,int id,int n){
	add_to_tree(id,n);
	
	int N = Q[id].size() + n;
	int parity = seg.calc(1,n,0,pos[root].fi,pos[root].fi);
	int cnt = seg.calc(1,n,0,1,n) + Q[id].size();
	
	clean_up(id,n);
	
	if (parity) return -1;
	
	return cnt + 2*(N - 1 - cnt);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
//	freopen("CLEANING.inp","r",stdin);
//	freopen("CLEANING.out","w",stdout);
	
	int n,q;
	cin >> n >> q;
	input(n,q);
	
	int root = get_root(n);
	prepare(root,n);
	
	for (int id = 1 ; id <= q ; id++)
	    cout << get_answer(root,id,n) << "\n";

	return 0;
}

• 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