Submission #697331

#	Time	Username	Problem	Language	Result	Execution time	Memory
697331		amirhoseinfar1385	Spring cleaning (CEOI20_cleaning)	C++17	0 / 100	104 ms	11088 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;
int kaf=(1<<18);
struct segment{
	int seg[(1<<19)];
	void upd(int i,int w){
		if(i==0){
			return ;
		}
		seg[i]+=w;
		return upd((i>>1),w);
	}
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		int d=pors((i<<1),l,m,tl,tr);
		d+=pors((i<<1)^1,m+1,r,tl,tr);
		return d;
	}
}seg;
int n,m;
vector<vector<int>>adj;
int timea=0;
vector<pair<int,int>>stf;
vector<int>high;
int rishe,mainres=0;

void dfs(int u,int par=0){
	high[u]=high[par]+1;
	timea++;
	stf[u].first=timea;
	for(auto x:adj[u]){
		if(x!=par){
			dfs(x,u);
		}
	}
	stf[u].second=timea;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	high.resize(n+1);
	stf.resize(n+1);
	adj.resize(n+1);
	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(adj[i].size()>1){
			rishe=i;
		}
	}
	dfs(rishe,0);
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(adj[i].size()==1){
			seg.upd(kaf+stf[i].first,1);
			cnt++;
		}
	}
	for(int i=1;i<=n;i++){
		if(i==rishe){
			continue;
		}
		int wtf=seg.pors(1,0,kaf-1,stf[i].first,stf[i].second);
		if(wtf&1){
			mainres+=1;
		}
		else{
			mainres+=2;
		}
	}
	vector<int>vis(n+1),visa(n+1);
	for(int asd=0;asd<m;asd++){
		int di;
		cin>>di;
		vector<int>alld(di);
		for(int i=0;i<di;i++){
			cin>>alld[i];
		}
		int fakemainres=mainres,fakecnt=cnt;
		for(auto x:alld){
			if((int)adj[x].size()==1&&vis[x]==0){
				vis[x]=1;
				continue;
			}
			vis[x]=1;
			fakecnt++;
			int td=seg.pors(1,0,kaf-1,stf[x].first,stf[x].second);
			if(td&1){
				int higha=high[x];
				fakemainres+=(higha+1)/2;
				fakemainres-=higha/2;
			}
			else{
				int higha=high[x];
				fakemainres-=(higha+1)/2;
				fakemainres+=higha/2;
			}
			seg.upd(kaf+stf[x].first,1);
		}
		if(fakecnt&1){
			cout<<-1<<"\n";
		}
		else{
			fakemainres+=di;
			cout<<fakemainres<<"\n";
		}
		for(auto x:alld){
			if((int)adj[x].size()==1&&visa[x]==0){
				visa[x]=1;
				continue;
			}
			visa[x]=1;
			seg.upd(kaf+stf[x].first,-1);
		}
		for(auto x:alld){
			visa[x]=vis[x]=0;
		}
	}
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30