Submission #1037971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037971		vjudge1	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	194 ms	39952 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 = 1e15;
const int MOD = 1e9 + 7;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

int s[4 * N];
int lz[4 * N];

int 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(l > tr || tl > r)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];
}

vector<int> g[N];
int sz[N];
int dep[N];
int par[N];
int tin[N], tout[N];

void dfs1(int x,int p){
	par[x] = p;
	vector<int> v;
	sz[x] = 1;
	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][i], g[x][0]);
	}
}

int T;
int top[N];

void dfs2(int x, bool t){
	tin[x] = ++T;
	if(t)top[x] = top[par[x]];
	else top[x] = x;
	for(int i = 0;i < g[x].size();i++){
		if(!i)dfs2(g[x][i], 1);
		else dfs2(g[x][i], 0);
	}
	tout[x] = T;
}

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

bool A[N];


signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int m;
	cin>>n>>m;
	int r;
	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);
	}
	for(int i = 0;i < n;i++){
		if(g[i].size() >= 2){
			r = i;
			break;
		}
	}
	dfs1(r, r);
	dfs2(r, 0);
	int cnt = 0;
	for(int i = 0;i < n;i++){
		if(g[i].empty())update(r, i), cnt++;
	}
//		assert(0);
	while(m--){
		int k;
		cin>>k;
		set<int> s;
		for(int i = 0;i < k;i++){
			int u;
			cin>>u;
			--u;
			A[u] ^= 1;
			s.insert(u);
		}
		int c = cnt;
		for(auto u: s)c -= g[u].empty();
		if((c + k) % 2){
			for(auto u:s) A[u] = 0;
			cout<<-1<<'\n';
			continue;
		}
		
		for(auto u: s){
			if((g[u].empty()) ^ A[u])update(r, u);
		}
		
		int q = get();
		cout<< k + n + q - 2<<'\n';
		
		for(auto u: s){
			if((g[u].empty()) ^ A[u])update(r, u);
		}
		for(auto u: s)A[u] = 0;
	}
	
}
 

Compilation message (stderr)

cleaning.cpp: In function 'void dfs1(long long int, long long int)':
cleaning.cpp:68: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]
   68 |  for(int i = 1;i < g[x].size();i++){
      |                ~~^~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs2(long long int, bool)':
cleaning.cpp:80: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]
   80 |  for(int i = 0;i < g[x].size();i++){
      |                ~~^~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:144:35: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |    if((g[u].empty()) ^ A[u])update(r, 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