Submission #697361

#	Time	Username	Problem	Language	Result	Execution time	Memory
697361		amirhoseinfar1385	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	290 ms	57456 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;
int inf=1e9+5;
int kaf=(1<<18);
struct segment{
	pair<int,int>seg[(1<<19)];
	vector<int>unnow;
	segment(){
		for(int i=0;i<(1<<19);i++){
			seg[i]=make_pair(inf,inf);
		}
	}
	void clear(){
		for(auto x:unnow){
			seg[x]=make_pair(inf,inf);
		}
		unnow.clear();
	}
	void upd(int i,int l,int r,int tl,int tr,pair<int,int>w){
		if(l>r||l>tr||r<tl){
			return ;
		}
		if(l>=tl&&r<=tr){
			unnow.push_back(i);
			seg[i]=min(seg[i],w);
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
	}
	pair<int,int>pors(int i){
		if(i==0){
			return seg[i];
		}
		pair<int,int>ret=min(seg[i],pors(i>>1));
		return ret;
	}
};
segment seg;

int n,m,rishe;
const int maxn=100000+5;
vector<int>bache[maxn],adj[maxn],fakeadj[maxn];
int timea=0,sz[maxn],fakesz[maxn],mainres=0,cnt=0,fakeres,fakecnt;
pair<int,int>stf[maxn],flca[20][maxn];
int lca[20][maxn],vis[maxn],high[maxn];
void dfs(int u,int par){
	high[u]=high[par]+1;
	timea++;
	lca[0][u]=par;
	stf[u].first=timea;
	for(auto x:adj[u]){
		if(x!=par){
			dfs(x,u);
			sz[u]+=sz[x];
			bache[u].push_back(x);
		}
	}
	if(adj[u].size()==1)
	{
		cnt++;
		sz[u]=1;
	}
	stf[u].second=timea;
	if((sz[u]&1)==0&&u!=rishe){
		mainres++;
	}
}

void callca(){
	for(int i=0;i<20;i++){
		for(int j=1;j<=n;j++){
			if(i==0){
				if(sz[j]&1){
					flca[i][j]=make_pair(1,0);
				}
				else{
					flca[i][j]=make_pair(0,1);
				}
				continue;
			}
			flca[i][j].first=flca[i-1][j].first+flca[i-1][lca[i-1][j]].first;
			flca[i][j].second=flca[i-1][j].second+flca[i-1][lca[i-1][j]].second;
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

bool cmp(int a,int b){
	return stf[a].first<stf[b].first;
}

bool zird(int u,int v){
	if(stf[u].first<=stf[v].first&&stf[u].second>=stf[v].second){
		return 1;
	}
	return 0;
}

int justlca(int u,int v){
	if(u==v){
		return u;
	}
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(int i=19;i>=0;i--){
		if(lca[i][u]==0){
			continue;
		}
		if(!zird(lca[i][u],v)){
			u=lca[i][u];
		}
	}
	u=lca[0][u];
	return u;
}

pair<int,int>getlca(int u,int v){
	if(u==v){
		return make_pair(0,0);
	}
	pair<int,int>ret={0,0};
	for(int i=19;i>=0;i--){
		if(lca[i][u]==0){
			continue;
		}
		if(!zird(lca[i][u],v)){
			ret.first+=flca[i][u].first;
			ret.second+=flca[i][u].second;
		//	cout<<i<<" "<<u<<" "<<v<<" "<<flca[i][u].first<<" "<<flca[i][u].second<<"\n";
			u=lca[i][u];
		}
	}
//	cout<<"paru "<<u<<" "<<v<<" "<<flca[0][u].first<<" "<<flca[0][u].second<<"\n";
	ret.first+=flca[0][u].first;
	ret.second+=flca[0][u].second;
	u=lca[0][u];
	return ret;
}

void solve(int u,int par=0){
	for(auto x:fakeadj[u]){
	//	cout<<"par:bach "<<u<<" "<<x<<"\n";
		solve(x,u);
		fakesz[u]+=fakesz[x];
	}
	//cout<<u<<" "<<fakesz[u]<<"\n";
	if(fakesz[u]&1){
		if(par!=0){
			pair<int,int>chen=getlca(u,par);
			fakeres-=chen.second;
			fakeres+=chen.first;
		}
	}
}

int main(){
//	freopen("input1.txt","r",stdin);
//	freopen("outy.txt","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if((int)adj[i].size()>1){
			rishe=i;
			break;
		}
	}
	dfs(rishe,0);
	callca();
	//cout<<mainres<<"\n";
	for(int asd=0;asd<m;asd++){
		//seg.clear();
		int di;
		cin>>di;
		vector<int>alld;
		vector<int>remove;
		fakeres=mainres,fakecnt=cnt;
		for(int i=0;i<di;i++){
			seg.clear();
			int dd;
			cin>>dd;
			remove.push_back(dd);
			alld.push_back(dd);
			if((int)adj[dd].size()==1&&vis[dd]==0){
				vis[dd]=1;
				continue;
			}
			fakecnt++;
			fakesz[dd]++;
		}
		if((int)alld.size()==0){
			//cout<<"salam\n";
			if(fakecnt&1){
				cout<<-1<<"\n";
			}
			else{
				fakeres+=n-1;
				fakeres+=di;
				cout<<fakeres<<"\n";
			}
			for(auto x:remove){
				fakeadj[x].clear();
				fakesz[x]=0;
				sz[x]=0;
				vis[x]=0;
			}
			continue;
		}
		//alld.push_back(rishe);	
		sort(alld.begin(),alld.end(),cmp);
		vector<int>fake=alld;
		for(int i=1;i<(int)alld.size();i++){
			fake.push_back(justlca(alld[i],alld[i-1]));
		}
		fake.push_back(rishe);
		sort(fake.begin(),fake.end());
		vector<int>alln;
		alln.push_back(fake[0]);
		for(int i=1;i<(int)fake.size();i++){
			if(fake[i]!=fake[i-1]){
				alln.push_back(fake[i]);
			}
		}
		sort(alln.begin(),alln.end(),cmp);
		for(int i=0;i<(int)alln.size();i++){
			pair<int,int>wp=seg.pors(kaf+stf[alln[i]].first);
		//	cout<<alln[i]<<" asd "<<wp.first<<" "<<wp.second<<"\n";
			if(wp.first!=inf){
				fakeadj[wp.second].push_back(alln[i]);
			}
			seg.upd(1,0,kaf-1,stf[alln[i]].first,stf[alln[i]].second,make_pair(-high[alln[i]],alln[i]));
		}
		solve(alln[0]);
		if(fakecnt&1){
			cout<<-1<<"\n";
		}
		else{
			fakeres+=n-1;
			fakeres+=di;
			cout<<fakeres<<"\n";
		}
		for(auto x:remove){
			fakeadj[x].clear();
			fakesz[x]=0;
			sz[x]=0;
			vis[x]=0;
		}
		for(auto x:alln){
			fakeadj[x].clear();
			fakesz[x]=0;
			sz[x]=0;
			vis[x]=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