oj.uz

Submission #302372

# Submission time Handle Problem Language Result Execution time Memory
302372 2020-09-18T16:03:55 Z errorgorn Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 485 ms 34808 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21532 KB Output is correct
2 Correct 233 ms 23604 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 22784 KB Output is correct
2 Correct 169 ms 22776 KB Output is correct
3 Correct 87 ms 28656 KB Output is correct
4 Correct 176 ms 27632 KB Output is correct
5 Correct 182 ms 29688 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 23164 KB Output is correct
2 Correct 215 ms 23284 KB Output is correct
3 Correct 103 ms 34808 KB Output is correct
4 Correct 437 ms 34640 KB Output is correct
5 Correct 91 ms 33400 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 24056 KB Output is correct
2 Correct 95 ms 23160 KB Output is correct
3 Correct 37 ms 22904 KB Output is correct
4 Correct 38 ms 23288 KB Output is correct
5 Correct 41 ms 23544 KB Output is correct
6 Correct 153 ms 23544 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 27000 KB Output is correct
2 Correct 485 ms 26872 KB Output is correct
3 Correct 364 ms 24568 KB Output is correct
4 Correct 454 ms 26880 KB Output is correct
5 Correct 456 ms 27000 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 30072 KB Output is correct
2 Correct 274 ms 32284 KB Output is correct
3 Correct 393 ms 31732 KB Output is correct
4 Correct 373 ms 32632 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21532 KB Output is correct
2 Correct 233 ms 23604 KB Output is correct
3 Correct 159 ms 22784 KB Output is correct
4 Correct 169 ms 22776 KB Output is correct
5 Correct 87 ms 28656 KB Output is correct
6 Correct 176 ms 27632 KB Output is correct
7 Correct 182 ms 29688 KB Output is correct
8 Correct 213 ms 23164 KB Output is correct
9 Correct 215 ms 23284 KB Output is correct
10 Correct 103 ms 34808 KB Output is correct
11 Correct 437 ms 34640 KB Output is correct
12 Correct 91 ms 33400 KB Output is correct
13 Correct 228 ms 24056 KB Output is correct
14 Correct 95 ms 23160 KB Output is correct
15 Correct 37 ms 22904 KB Output is correct
16 Correct 38 ms 23288 KB Output is correct
17 Correct 41 ms 23544 KB Output is correct
18 Correct 153 ms 23544 KB Output is correct
19 Correct 258 ms 27000 KB Output is correct
20 Correct 485 ms 26872 KB Output is correct
21 Correct 364 ms 24568 KB Output is correct
22 Correct 454 ms 26880 KB Output is correct
23 Correct 456 ms 27000 KB Output is correct
24 Correct 420 ms 30072 KB Output is correct
25 Correct 274 ms 32284 KB Output is correct
26 Correct 393 ms 31732 KB Output is correct
27 Correct 373 ms 32632 KB Output is correct
28 Correct 332 ms 26616 KB Output is correct
29 Correct 365 ms 31288 KB Output is correct
30 Correct 182 ms 29680 KB Output is correct
31 Correct 397 ms 34544 KB Output is correct
32 Correct 454 ms 26876 KB Output is correct
33 Correct 443 ms 29944 KB Output is correct
34 Correct 459 ms 31996 KB Output is correct
35 Correct 475 ms 31848 KB Output is correct