제출 #602925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602925		vanic	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	293 ms	18276 KiB

cleaning

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int maxn=1e5+5, Log=17, pot=(1<<Log);

struct tournament{
	int t[pot*2];
	bool prop[pot*2];
	int vel[pot*2];
	tournament(){
		for(int i=pot; i<pot*2; i++){
			vel[i]=1;
		}
		for(int i=pot-1; i>0; i--){
			vel[i]=vel[i*2]*2;
		}
	}
	void propagate(int x){
		if(prop[x]){
			t[x]=vel[x]-t[x];
			if(x<pot){
				prop[x*2]^=1;
				prop[x*2+1]^=1;
			}
			prop[x]=0;
		}
	}
	void update(int x, int val){
		t[x]=val;
		for(x/=2; x>0; x/=2){
			propagate(x*2);
			propagate(x*2+1);
			t[x]=t[x*2]+t[x*2+1];
		}
	}
	void update2(int L, int D, int x, int l, int d){
		propagate(x);
		if(L>=l && D<=d){
//			cout << "flip " << L << ' ' << D << endl;
			update(x, vel[x]-t[x]);
			if(x<pot){
				prop[x*2]^=1;
				prop[x*2+1]^=1;
			}
			return;
		}
		if((L+D)/2>=l){
			update2(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			update2((L+D)/2+1, D, x*2+1, l, d);
		}
	}
	int query(int L, int D, int x, int l, int d){
		propagate(x);
		if(L>=l && D<=d){
			return t[x];
		}
		int lijeva=0, desna=0;
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d);
		}
		return lijeva+desna;
	}
};

tournament T;
vector < int > ms[maxn];
int novi[maxn];
bool p[maxn];
int list;
int root;


int djeca[maxn];
int parent[maxn];


int dfs2(int x, int prosl){
	parent[x]=prosl;
	djeca[x]=1;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			djeca[x]+=dfs2(ms[x][i], x);
		}
	}
	return djeca[x];
}

int gornji[maxn];
int pos[maxn];
int boja[maxn];
int tren, koji;

void odredi(int x, int prosl){
	boja[x]=tren;
	pos[x]=koji;
	koji++;
	if(gornji[tren]==-1){
		gornji[tren]=x;
	}
	
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl && djeca[ms[x][i]]*2>=djeca[x]){
			odredi(ms[x][i], x);
		}
	}
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl && djeca[ms[x][i]]*2<djeca[x]){
			tren++;
			odredi(ms[x][i], x);
		}
	}
}


int dfs(int x, int prosl){
	int br=0;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			br+=dfs(ms[x][i], x);
		}
	}
	if(x==prosl){
		if(br&1){
//			cout << x << " je " << pos[x] << endl;
			T.update(pos[x]+pot, 1);
		}
		return br;
	}
	if(!br){
		list++;
		br++;
	}
	if(!(br&1)){
//		cout << x << " je " << pos[x] << endl;
		T.update(pos[x]+pot, 1);
	}
	return br;
}


void scan(int &a){
	a=0;
	char c=getchar_unlocked();
	while(c>='0' && c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar_unlocked();
	}
}


void update(int x){
//	cout << "za " << x << " je " << pos[gornji[boja[x]]] << ' ' << pos[x] << endl;
	T.update2(0, pot-1, 1, pos[gornji[boja[x]]], pos[x]);
	if(parent[gornji[boja[x]]]==gornji[boja[x]]){
		return;
	}
	update(parent[gornji[boja[x]]]);
}

int main(){
	int n, q;
	scan(n);
	scan(q);
	int a, b;
	for(int i=0; i<n-1; i++){
		scan(a);
		scan(b);
		a--;
		b--;
		ms[a].push_back(b);
		ms[b].push_back(a);
	}
	for(int i=0; i<n; i++){
		if(ms[i].size()>1){
			root=i;
			break;
		}
	}
	memset(gornji, -1, sizeof(gornji));
	dfs2(root, root);
	odredi(root, root);
	dfs(root, root);
	int m;
	int liste;
	for(int i=0; i<q; i++){
		liste=list;
		scan(m);
		for(int j=0; j<m; j++){
			scan(a);
			a--;
			novi[j]=a;
			if(ms[a].size()==1 && !p[a]){
				p[a]=1;
			}
			else{
				liste++;
				update(a);
			}
		}
//		cout << "ost " << T.t[1] << endl;
		if(liste&1){
			printf("-1\n");
		}
		else{
//			cout << "aha " << T.query(0, pot-1, 1, 0, 0) << endl;
			printf("%d\n", n-1+m+T.t[1]);
		}
		for(int j=0; j<m; j++){
			if(ms[novi[j]].size()==1 && p[novi[j]]){
				p[novi[j]]=0;
			}
			else{
				update(novi[j]);
			}
		}
	}
	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