Submission #291190

#	Time	Username	Problem	Language	Result	Execution time	Memory
291190		TadijaSebez	Spring cleaning (CEOI20_cleaning)	C++11	100 / 100	409 ms	17544 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
int deg[N];
vector<int> E[N];
const int M=2*N;
int root,ls[M],rs[M],sum[M],tsz,lzy[M];
void Flip(int&c,int ss,int se,int qs,int qe){
	if(qs>qe||qs>se||ss>qe)return;
	if(!c)c=++tsz;
	if(qs<=ss&&qe>=se){sum[c]=se-ss+1-sum[c];lzy[c]^=1;return;}
	int mid=ss+se>>1;
	Flip(ls[c],ss,mid,qs,qe);
	Flip(rs[c],mid+1,se,qs,qe);
	sum[c]=sum[ls[c]]+sum[rs[c]];
	if(lzy[c])sum[c]=se-ss+1-sum[c];
}
int head[N],lid[N],rid[N],tid,sz[N],par[N];
void DFS(int u,int p){
	sz[u]=1;par[u]=p;
	for(int v:E[u])if(v!=p)DFS(v,u),sz[u]+=sz[v];
}
void HLD(int u,int p){
	lid[u]=++tid;
	if(!head[u])head[u]=u;
	int hc=0;
	for(int v:E[u])if(v!=p&&sz[hc]<sz[v])hc=v;
	if(hc!=0){
		head[hc]=head[u];
		HLD(hc,u);
		for(int v:E[u])if(v!=p&&v!=hc)HLD(v,u);
	}
	rid[u]=tid;
}
void Flip(int u){
	while(u>0){
		Flip(root,2,tid,lid[head[u]],lid[u]);
		u=par[head[u]];
	}
}
int main(){
	int n,q;
	scanf("%i %i",&n,&q);
	for(int i=1,u,v;i<n;i++){
		scanf("%i %i",&u,&v);
		E[u].pb(v);E[v].pb(u);
		deg[u]++;deg[v]++;
	}
	DFS(1,0);
	HLD(1,0);
	int leaf=0;
	for(int i=1;i<=n;i++)if(deg[i]==1)Flip(i),leaf++;
	for(int i=1;i<=q;i++){
		int k;scanf("%i",&k);
		vector<int> p(k);
		for(int&j:p){
			scanf("%i",&j);
			deg[j]++;
			if(deg[j]!=2){
				leaf++;
				Flip(j);
			}
		}
		if(leaf%2==1)printf("-1\n");
		else printf("%i\n",n-1+k+n-1-sum[root]);
		reverse(p.begin(),p.end());
		for(int j:p){
			deg[j]--;
			if(deg[j]!=1){
				leaf--;
				Flip(j);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

cleaning.cpp: In function 'void Flip(int&, int, int, int, int)':
cleaning.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |  int mid=ss+se>>1;
      |          ~~^~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%i %i",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |   scanf("%i %i",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   int k;scanf("%i",&k);
      |         ~~~~~^~~~~~~~~
cleaning.cpp:58:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |    scanf("%i",&j);
      |    ~~~~~^~~~~~~~~

• 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