Submission #302372

#	Time	Username	Problem	Language	Result	Execution time	Memory
302372		errorgorn	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	485 ms	34808 KiB

cleaning

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());


int n,q;
vector<int> al[100005];
int in[100005]; //preorder
int out[100005]; //postorder
int st[100005]; //subtree size
int parent[100005]; //first parent
int hparent[100005]; //parent on heavy path
int depth[100005];

bool par[100005];
int extra[100005];

ll ans;

int dfs(int i,int p){
	int ropes=0;
	if (sz(al[i])==1){
		ans+=depth[i];
		par[i]=true;
		ropes=1;
	}
	
	for (auto &it:al[i]){
		if (it==p) continue;
	
		depth[it]=depth[i]+1;
		ropes+=dfs(it,i);
		par[i]^=par[it];
	}
	
	while (ropes>2){
		ropes-=2;
		ans-=2*depth[i];
	}
	
	return ropes;
}

void dfs_st(int i,int p){
    parent[i]=p;
    st[i]=1;
    if (al[i][0]==p && al[i].size()>1) swap(al[i][0],al[i][1]);
    for (auto &it:al[i]){ ///& is important here
        if (it==p) continue;
        dfs_st(it,i);
        st[i]+=st[it];
        if (st[it]>st[al[i][0]]){
            swap(it,al[i][0]);
            //we ensure heavy child is al[i][0]
        }
    }
}

int dfs_time=0;
void dfs_hld(int i,int p){
    in[i]=++dfs_time;
    for (auto it:al[i]){
        if (it==p) continue;
        hparent[it]=(it==al[i][0])?hparent[i]:it;
        dfs_hld(it,i);
    }
    out[i]=dfs_time;
}

struct node{
	int s,e,m;
	int bits[2];
	bool lazy=false;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		bits[0]=bits[1]=0;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void init(int i,int k){
		bits[k]++;
		if (s==e) return;
		else if (i<=m) l->init(i,k);
		else r->init(i,k);
	}
	
	void propo(){
		if (lazy){
			swap(bits[0],bits[1]);
			
			if (s!=e){
				l->lazy^=true;
				r->lazy^=true;
			}
			lazy=false;
		}
	}
	
	void update(int i,int j){
		if (s==i && e==j) lazy^=true;
		else{
			if (j<=m) l->update(i,j);
			else if (m<i) r->update(i,j);
			else l->update(i,m),r->update(m+1,j);
			
			l->propo(),r->propo();
			rep(x,0,2) bits[x]=l->bits[x]+r->bits[x];
		}
	}
	
	int query(int i,int j){
		propo();
		if (s==i && e==j) return bits[1];
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return l->query(i,m)+r->query(m+1,j);
	}
} *root=new node(0,200005);

void hld_query(int i,bool flag){
    while (i){
		if (flag){
			root->update(in[hparent[i]],in[i]);
			ans-=2*root->query(in[hparent[i]],in[i]);
		}
		else{
			ans+=2*root->query(in[hparent[i]],in[i]);
			root->update(in[hparent[i]],in[i]);
		}
		i=parent[hparent[i]];
	}
	
	if (root->query(in[1],in[1])==flag){
		if (flag) ans+=2;
		else ans-=2;
	}
}

vector<int> v;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>q;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].push_back(b);
		al[b].push_back(a);
	}
	
	dfs(1,-1);
	//cout<<ans<<endl;
	
	parent[1]=0;
	hparent[1]=1;
	if (n>=2){
    	dfs_st(1,-1);
    	dfs_hld(1,-1);
	}
	
	rep(x,1,n+1) root->init(in[x],par[x]);
	
	while (q--){
		v.clear();
		cin>>a;
		rep(x,0,a){
			cin>>b;
			v.push_back(b);
		}
		
		for (auto &it:v){
			if (sz(al[it])==1 && extra[it]==0){
				ans++;
			}
			else{
				ans+=depth[it]+1;
				hld_query(it,true);
			}
			
			extra[it]++;
		}
		
		if (root->query(in[1],in[1])) cout<<"-1"<<endl;
		else cout<<ans<<endl;
		
		for (auto &it:v){
			extra[it]--;
			
			if (sz(al[it])==1 && extra[it]==0){
				ans--;
			}
			else{
				ans-=depth[it]+1;
				hld_query(it,false);
			}
		}
	}
}

Compilation message (stderr)

cleaning.cpp: In constructor 'node::node(int, int)':
cleaning.cpp:100:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

• 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