oj.uz

Submission #754432

# Submission time Handle Problem Language Result Execution time Memory
754432 2023-06-07T18:49:05 Z NintsiChkhaidze Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 384 ms 21444 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,((l + r)>>1)
#define right ((h<<1)|1),((l + r)>>1) + 1,r
#define pii pair <int,int>
using namespace std;

const int N = 2e5 + 5;

vector <int> v[N];
int head[N],heavy[N],timer,tin[N],lz[4*N];
int parent[N],t[4*N],n,fix[N],sub[N],root;
vector <pii> vec;

void push(int h,int l,int r){
	if (!lz[h]) return;
	lz[h*2] ^= 1;
	lz[h*2+1]^=1;
	int mid=(l+r)/2;
	t[h*2]=(mid - l + 1) - t[h*2];
	t[h*2+1] = (r - mid) - t[h*2 + 1];
	lz[h]=0;
}
void upd(int h,int l,int r,int L,int R){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		lz[h] ^= 1;
		t[h] = (r - l + 1) - t[h];
		return;
	}
	push(h,l,r);
	upd(left,L,R);
	upd(right,L,R);
	t[h] = t[h*2] + t[h*2 + 1];
}

void dfs(int x){
	sub[x] = 1;

	for (int to: v[x]){
		if (to == parent[x]) continue;

		parent[to] = x;
		dfs(to);
		sub[x] += sub[to];
		
		if (sub[to] > sub[heavy[x]]) heavy[x] = to;
	}

}

void dfs2(int x,int hh){
	head[x] = hh;
	tin[x] = ++timer;
	if (heavy[x]) dfs2(heavy[x],hh);

	for (int to: v[x]){
		if (to==parent[x] || to == heavy[x]) continue;
		dfs2(to,to);
	}
}

void update(int x){
	while (x != root){
		upd(1,1,n,tin[head[x]],tin[x]);
		if (head[x] == root) return;
		x = parent[head[x]];
	}
	upd(1,1,n,1,1);
}

int main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int m;
	cin>>n>>m;
	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	// for (int i= 1; i <= n; i++){
	// 	if (v[i].size() > 1) {root = i; break;}
	// }

	root = 1;
	dfs(root);
	dfs2(root,root);

	int LL=0;
	for (int i = 1; i <= n; i++){
		if (v[i].size() == 1) update(i),LL++;
	}

	for (int j = 1; j <= m; j++){
		int x;
		cin>>x;
		int L=LL;

		vector <int> vert;
		for (int i = 1; i <= x; i++){
			int nd;
			cin>>nd;

			if (!fix[nd] && v[nd].size() == 1){
				--L;
				fix[nd] = 1;
			}
			else {
				update(nd);
				
			}
			vert.pb(nd);
		}
		L += x;

		if (!(L%2))
			cout<<2*n + x - 2 - t[1]<<endl;
		else 
			cout<<-1<<endl;

		for (int y: vert) fix[y]=0;
		for (int nd: vert){
			if (!fix[nd] && v[nd].size() == 1){
				--L;
				fix[nd] = 1;
			}
			else {
				update(nd);
			}
		}
		for (int y: vert) fix[y]=0;
	}
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 107 ms 7456 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6188 KB Output is correct
2 Correct 45 ms 6404 KB Output is correct
3 Correct 73 ms 13124 KB Output is correct
4 Correct 90 ms 12408 KB Output is correct
5 Correct 102 ms 14276 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6804 KB Output is correct
2 Correct 48 ms 6860 KB Output is correct
3 Correct 58 ms 21444 KB Output is correct
4 Correct 107 ms 21120 KB Output is correct
5 Correct 51 ms 18876 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8008 KB Output is correct
2 Correct 45 ms 6972 KB Output is correct
3 Correct 24 ms 6860 KB Output is correct
4 Correct 20 ms 7464 KB Output is correct
5 Correct 17 ms 7552 KB Output is correct
6 Correct 46 ms 7500 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 11172 KB Output is correct
2 Correct 271 ms 11012 KB Output is correct
3 Correct 181 ms 8216 KB Output is correct
4 Correct 243 ms 10920 KB Output is correct
5 Correct 224 ms 10928 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 15028 KB Output is correct
2 Correct 255 ms 17704 KB Output is correct
3 Correct 324 ms 17076 KB Output is correct
4 Correct 263 ms 18316 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 107 ms 7456 KB Output is correct
3 Correct 43 ms 6188 KB Output is correct
4 Correct 45 ms 6404 KB Output is correct
5 Correct 73 ms 13124 KB Output is correct
6 Correct 90 ms 12408 KB Output is correct
7 Correct 102 ms 14276 KB Output is correct
8 Correct 45 ms 6804 KB Output is correct
9 Correct 48 ms 6860 KB Output is correct
10 Correct 58 ms 21444 KB Output is correct
11 Correct 107 ms 21120 KB Output is correct
12 Correct 51 ms 18876 KB Output is correct
13 Correct 66 ms 8008 KB Output is correct
14 Correct 45 ms 6972 KB Output is correct
15 Correct 24 ms 6860 KB Output is correct
16 Correct 20 ms 7464 KB Output is correct
17 Correct 17 ms 7552 KB Output is correct
18 Correct 46 ms 7500 KB Output is correct
19 Correct 235 ms 11172 KB Output is correct
20 Correct 271 ms 11012 KB Output is correct
21 Correct 181 ms 8216 KB Output is correct
22 Correct 243 ms 10920 KB Output is correct
23 Correct 224 ms 10928 KB Output is correct
24 Correct 384 ms 15028 KB Output is correct
25 Correct 255 ms 17704 KB Output is correct
26 Correct 324 ms 17076 KB Output is correct
27 Correct 263 ms 18316 KB Output is correct
28 Correct 177 ms 10820 KB Output is correct
29 Correct 157 ms 16796 KB Output is correct
30 Correct 110 ms 14372 KB Output is correct
31 Correct 95 ms 21060 KB Output is correct
32 Correct 246 ms 10924 KB Output is correct
33 Correct 140 ms 15564 KB Output is correct
34 Correct 149 ms 17560 KB Output is correct
35 Correct 190 ms 17376 KB Output is correct