Submission #1039397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039397		ZeroCool	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	200 ms	40016 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ar array
#define ld long double
 
const int N = 2e5 + 20;
const int INF = 1e16;
const int MOD = 1e9 + 7;
const ld EPS = 1e-9;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

int n, A[N], in[N], dep[N], par[N], top[N], sz[N], T;
vector<int> g[N];

namespace SGT{
	int s[4 * N], lz[4 * N];
	void push(int k,int tl, int tr){
		if(!lz[k])return;
		s[k] = tr - tl + 1 - s[k];	
		if(tl != tr){
			lz[k * 2] ^= lz[k];
			lz[k * 2 + 1] ^= lz[k];
		}
		lz[k] = 0;
	}
	void upd(int k,int tl,int tr,int l,int r){
		push(k, tl, tr);
		if(tl >r || l > tr)return;
		if(l <= tl && tr <= r){
			lz[k] ^= 1;
			push(k, tl, tr);
			return;
		}
		int tm = (tl + tr) / 2;
		upd(k * 2, tl, tm, l,r );
		upd(k *2 + 1, tm + 1, tr, l, r);
		s[k] = s[k * 2] + s[k * 2 + 1];
	}
	
	int get(){
		push(1, 1, n);
		return n - s[1];
	}
}

void dfs1(int x,int p){
	vector<int> v;
	sz[x] = 1;
	par[x] = p;
	for(auto u: g[x]){
		if(u == p)continue;
		v.push_back(u);
		dep[u] = dep[x] + 1;
		dfs1(u, x);
		sz[x] += sz[u];
	}
	g[x] = v;
	for(int i = 1;i < g[x].size();i++){
		if(sz[g[x][i]] > sz[g[x][0]])swap(g[x][0], g[x][i]);
	}
}

void dfs2(int x,bool t){
	if(!t)top[x] = top[par[x]];
	else top[x] = x;
	in[x] = ++T;
	int p = 0;
	for(auto u: g[x])dfs2(u, p++);
}

void upd(int u,int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]])swap(u, v);
		SGT::upd(1, 1, n, in[top[u]], in[u]);
		u = par[top[u]];
	}
	if(dep[u] > dep[v])swap(u, v);
	SGT::upd(1, 1, n, in[u], in[v]);
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int q;
	cin>>n>>q;
	for(int i = 1;i < n;i++){
		int u, v;
		cin>>u>>v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int r = 0;
	for(int i = 0;i < n;i++){
		if(g[i].size() >= 2){
			r = i;
			break;
		}
	}
	dfs1(r, r);
	dfs2(r, 1);
	int cnt = 0;
	for(int i = 0;i  <n;i++){
		if(g[i].empty())upd(i, r), cnt++;
	}
	//cout<<cnt<<'\n';
	while(q--){
		int k;
		cin>>k;
		set<int> s;
		for(int i = 0;i < k;i++){
			int u;
			cin>>u;
			--u;
			s.insert(u);
			A[u] ^= 1;
		}
		int nc = cnt;
		for(auto u: s){
			if(g[u].empty())--nc;
		}
		if((nc + k) % 2){
			cout<<-1<<'\n';;
			for(auto u: s)A[u] = 0;
			continue;
		}
		for(auto u: s){
			if(g[u].empty() != A[u])upd(u, r);
		}
		cout<<n + k + SGT::get() - 2<<'\n';
		for(auto u: s){
			if(g[u].empty() != A[u])upd(u, r);
		}
		for(auto u: s)A[u] = 0;
	}
}


 

Compilation message (stderr)

cleaning.cpp: In function 'void dfs1(long long int, long long int)':
cleaning.cpp:62:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 1;i < g[x].size();i++){
      |                ~~^~~~~~~~~~~~~

• 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