Submission #868239

#	Time	Username	Problem	Language	Result	Execution time	Memory
868239		Hakiers	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	222 ms	27604 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
const int BASE = 1 << 17;
vector<int> G[BASE];
int dp[BASE];
int sajz[BASE];
int LAZY[BASE << 1];
int TREE[BASE << 1][2];
int path_end[BASE];
int pre[BASE];
int parent[BASE];
int depth[BASE];
int tajm;
int n, q;

void push(int v, int l, int r){
	
	if(!LAZY[v]) return;
	LAZY[l] ^= LAZY[v];
	LAZY[r] ^= LAZY[v];
	
	swap(TREE[l][0], TREE[l][1]);
	swap(TREE[r][0], TREE[r][1]);
	LAZY[v] = 0;
}

void add(int a, int b, int v, int l, int r, int x){
	if(b < l || r < a) return;
	else if(l <= a && b <= r){
		TREE[v][x] = 1;
	}
	else{
		int mid = (a+b)/2;
		push(v, 2*v, 2*v+1);
		add(a, mid, 2*v, l, r, x);
		add(mid+1, b, 2*v + 1, l, r, x);
		TREE[v][0] = TREE[2*v][0] + TREE[2*v+1][0];
		TREE[v][1] = TREE[2*v][1] + TREE[2*v+1][1];
	}
}

void update(int a, int b, int v, int l, int r, int x){
	if(b < l || r < a) return;
	else if(l <= a && b <= r){
		swap(TREE[v][0], TREE[v][1]);
		LAZY[v] ^= x;
	}
	else{
		int mid = (a+b)/2;
		push(v, 2*v, 2*v+1);
		update(a, mid, 2*v, l, r, x);
		update(mid +1, b, 2*v+1, l, r, x);
		TREE[v][0] = TREE[2*v][0] + TREE[2*v+1][0];
		TREE[v][1] = TREE[2*v][1] + TREE[2*v+1][1];
	}
}

pair<int, int> query(int a, int b, int v, int l, int r){
	if(b < l || r < a) return {0, 0};
	else if(l <= a && b <= r){
		return {TREE[v][0], TREE[v][1]};
	}
	else{
		int mid = (a+b)/2;
		push(v, 2*v, 2*v+1);
		pair<int, int> p1 = query(a, mid, 2*v, l, r);
		pair<int, int> p2 = query(mid+1, b, 2*v+1, l, r);
		
		return {p1.first+p2.first, p1.second+p2.second};
	}
}

void dfs_size(int v, int p){
	sajz[v] = 1;
	for(auto u : G[v]){
		if(u == p) continue;
		dfs_size(u, v);
		sajz[v] += sajz[u];
	}
}


void hld(int v, int p){
	pre[v] = ++tajm;
	parent[v] = p;
	depth[v] = depth[p] + 1;
	int maxpath = 0;
	for(auto u : G[v])
		if(u != p && sajz[u] > sajz[maxpath]) maxpath = u;
		
	
	if(maxpath){
		path_end[maxpath] = path_end[v];
		hld(maxpath, v);
	}
	
	for(auto u : G[v]){
		if(u == p || u == maxpath) continue;
		path_end[u] = u;
		hld(u, v);
	}
}

void dfs_dp(int v, int p){
	if(G[v].size() == 1)
		dp[v] = 1;
		
	for(auto u : G[v]){
		if(u == p) continue;
		dfs_dp(u, v);
		dp[v] += dp[u];
	}
	
	add(0, BASE-1, 1, pre[v], pre[v], (dp[v]&1));
}


void no(){
	cout << "-1\n";
}

void yes(int howadd){
	//pair<int, int> query2 = query(0, BASE-1, 1, pre[1]+1, BASE-1);
	pair<int, int> query2 = {TREE[1][0] - 1, TREE[1][1]};
	howadd += query2.first *2;
	howadd += query2.second;
	
	cout << howadd << "\n";
}

void zmien(int u, int v){

	if(depth[u] < depth[v]) swap(u, v);
	
	while(path_end[u] != path_end[v]){
		update(0, BASE-1, 1, pre[path_end[u]], pre[u], 1);
		u = parent[path_end[u]];
	}
	
	update(0, BASE-1, 1, pre[v], pre[u], 1);

}

void solve(){
	multiset<int> nodes;
	set<int> nodesS;
	vector<int> zmiany;
	int D;
	cin >> D;
	
	for(int i = 1; i <= D; i++){
		int v;
		cin >> v;
		nodes.insert(v);
		nodesS.insert(v);
	}
	
	int howadd = 0;
	for(auto v : nodesS){
		int countv = nodes.count(v);
		howadd += countv;
		if(G[v].size() == 1 && !(countv&1)){
			//cout << "v:" << v << "count" << countv << endl;
			zmien(1, v);
			zmiany.push_back(v);
		}
		else if(G[v].size() > 1 && countv&1){
			zmien(1, v);
			zmiany.push_back(v);
		}
	}
	
	pair<int, int> query1 = query(0, BASE-1, 1, pre[1], pre[1]);
	
	if(!query1.first) no();
	else yes(howadd);
	
	for(auto v : zmiany)
		zmien(1, v);
	
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i < n; i++){
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	dfs_size(1, 1);
	hld(1, 1);
	dfs_dp(1, 1);
	
	while(q--)
		solve();

}

• 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