oj.uz

Submission #578131

# Submission time Handle Problem Language Result Execution time Memory
578131 2022-06-16T05:35:52 Z amunduzbaev Spring cleaning (CEOI20_cleaning) C++17
26 / 100
 135 ms 23756 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;

const int N = 1e5 + 5;
vector<int> edges[N];
int sub[N], add[N], is[N];
int d[N], par[N][20], pref[N];
int tin[N], tout[N], t, res;

void dfs(int u, int p = -1){
	tin[u] = ++t;
	for(int j=1;j<20;j++){
		par[u][j] = par[par[u][j-1]][j-1];
	}
	for(auto x : edges[u]){
		if(x == p) continue;
		d[x] = d[u] + 1;
		par[x][0] = u;
		dfs(x, u);
		sub[u] += sub[x];
	}
	
	if(!sub[u]) sub[u] = 1, is[u] = 1;
	tout[u] = t;
}

void dfs2(int u, int p = -1){
	sub[u] &= 1;
	res += (!sub[u]);
	pref[u] += sub[u];
	for(auto x : edges[u]){
		if(x == p) continue;
		pref[x] = pref[u];
		dfs2(x, u);
	}
}

bool isp(int a, int b) { return (tin[a] <= tin[b] && tin[b] <= tout[a]); }
int lca(int a, int b){
	if(isp(a, b)) return a;
	if(isp(b, a)) return b;
	for(int j=19;~j;j--){
		if(!isp(par[a][j], b)) a = par[a][j];
	}
	
	return par[a][0];
}

int solve(vector<int> t){
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	sort(t.begin(), t.end(), [&](int a, int b){
		return tin[a] < tin[b];
	});
	int m = t.size();
	for(int i=1;i<m;i++){
		t.push_back(lca(t[i-1], t[i]));
	}
	
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	sort(t.begin(), t.end(), [&](int a, int b){
		return tin[a] < tin[b];
	});
	
	int tot = 0;
	function<int(int)> dfs = [&](int i){
		int mx = i + 1, u = t[i];
		while(mx < (int)t.size() && tin[t[mx]] < tout[t[i]]){
			int x = t[mx];
			mx = dfs(mx);
			
			if(add[x] & 1){
				tot -= (d[x] - d[u] - pref[x] + pref[u]);
				tot += (pref[x] - pref[u]);
			}
			
			add[u] += add[x];
		}
		
		if(!i && (add[u]&1)){
			tot -= (d[u] - pref[u]);
			tot += pref[u];
		}
		
		return mx;
	};
	dfs(0);
	for(auto x : t) add[x] = 0;
	return tot;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin>>n>>q;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	int r = -1;
	for(int i=1;i<=n;i++){
		if((int)edges[i].size() > 1) { r = i; break; }
	}
	
	assert(~r);
	
	par[r][0] = d[r] = 1;
	dfs(r);
	dfs2(r);
	//~ cout<<res<<"\n";
	int cnt = accumulate(is + 1, is + n + 1, 0);
	
	for(int i=0;i<q;i++){
		int d; cin>>d;
		//~ cout<<"here"<<endl;
		vector<int> t;
		int tmp = 0;
		for(int x=0;x<d;x++){
			int p; cin>>p;
			//~ nw[p]++;
			t.push_back(p);
			add[p]++, tmp++;
			if(is[p]){
				is[p]--;
				cnt--;
				add[p]--;
			}
		}
		
		if((cnt + d) & 1){
			cout<<-1<<"\n";
		} else {
			
			//~ cout<<n - 1<<" "<<tmp<<" "<<res<<" "<<solve(t)<<"\n";
			cout<<n - 1 + tmp + res + solve(t) - 1<<"\n";
		}
		
		for(auto p : t){
			add[p] = 0;
			if((int)edges[p].size() == 1 && !is[p]){
				is[p] = 1;
				cnt++;
			}
		}
	}
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 57 ms 5460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 3920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4564 KB Output is correct
2 Correct 11 ms 4312 KB Output is correct
3 Correct 60 ms 23756 KB Output is correct
4 Correct 79 ms 22980 KB Output is correct
5 Correct 64 ms 21532 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 6188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 11904 KB Output is correct
2 Incorrect 119 ms 11736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 16848 KB Output is correct
2 Correct 119 ms 21572 KB Output is correct
3 Correct 135 ms 21540 KB Output is correct
4 Correct 117 ms 21024 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 57 ms 5460 KB Output isn't correct
3 Halted 0 ms 0 KB -