oj.uz

Submission #342448

# Submission time Handle Problem Language Result Execution time Memory
342448 2021-01-02T06:53:11 Z mario05092929 Spring cleaning (CEOI20_cleaning) C++11
100 / 100
 518 ms 21272 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 2e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,Q,co,tpos[100005],rtpos[100005],p[100005],up[100005];
int dep[100005],sz[100005];
int root,a[100005],ans;
int t0[400005],t1[400005];
int lazy[400005],leaf;
int isleaf[100005];
int cn[100005];
vec v[100005];

void dfs(int x,int pr,int depth) {
	sz[x] = 1, dep[x] = depth;
	for(int i : v[x]) {
		if(i == pr) continue;
		dfs(i,x,depth+1);
		p[i] = x;
		sz[x] += sz[i];
	}
}

bool cmp(int x,int y) {return sz[x] > sz[y];}

void dfs2(int x,int pr,int la) {
	sort(all(v[x]),cmp);
	tpos[x] = ++co, up[x] = la;
	rtpos[co] = x;
	int ch = 1;
	for(int i : v[x]) {
		if(i == pr) continue;
		if(ch) {dfs2(i,x,la), ch = 0;}
		else dfs2(i,x,i);
	}
}

int dfs3(int x,int pr) {
	int sum = (v[x].size() == 1);
	leaf += sum;
	isleaf[x] = sum;
	for(int i : v[x]) {
		if(i == pr) continue;
		int tmp = dfs3(i,x);
		if(tmp) ans++;
		else ans += 2;
		a[i] = tmp;
		sum += tmp;
	}
	sum %= 2;
	return sum;
}

void build(int x,int l,int r) {
	if(l == r) {
		t0[x] = (a[rtpos[l]] == 0);
		t1[x] = (a[rtpos[l]] == 1);
		return;
	}
	int mid = (l + r) >> 1;
	build(x*2,l,mid), build(x*2+1,mid+1,r);
	t0[x] = t0[x*2]+t0[x*2+1];
	t1[x] = t1[x*2]+t1[x*2+1];
}

void push(int x,int l,int r) {
	if(lazy[x]) {
		swap(t0[x],t1[x]);
		if(l^r) lazy[x*2] ^= 1, lazy[x*2+1] ^= 1;
		lazy[x] = 0;
	}
}

void update(int x,int l,int r,int rl,int rr) {
	push(x,l,r);
	if(rl > r||l > rr) return;
	if(rl <= l&&r <= rr) {
		lazy[x] ^= 1, push(x,l,r);
		return;
	}
	int mid = (l + r) >> 1;
	update(x*2,l,mid,rl,rr), update(x*2+1,mid+1,r,rl,rr);
	t0[x] = t0[x*2]+t0[x*2+1];
	t1[x] = t1[x*2]+t1[x*2+1];
}

pi query(int x,int l,int r,int rl,int rr) {
	push(x,l,r);
	if(rl > r||l > rr) return {0,0};
	if(rl <= l&&r <= rr) return {t0[x],t1[x]};
	int mid = (l + r) >> 1;
	pi L = query(x*2,l,mid,rl,rr), R = query(x*2+1,mid+1,r,rl,rr);
	return {L.x+R.x,L.y+R.y};
}

pi queryLCA(int x,int y) {
	pi ret = {0,0};
	while(up[x]^up[y]) {
		if(dep[up[x]] < dep[up[y]]) swap(x,y);
		pi tmp = query(1,1,n,tpos[up[x]],tpos[x]);
		update(1,1,n,tpos[up[x]],tpos[x]);
		ret.x += tmp.x, ret.y += tmp.y;
		x = p[up[x]];
	}
	if(x^y) {
		if(dep[x] > dep[y]) swap(x,y);
		pi tmp = query(1,1,n,tpos[x]+1,tpos[y]);
		update(1,1,n,tpos[x]+1,tpos[y]);
		ret.x += tmp.x, ret.y += tmp.y;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> Q;
	for(int i = 1;i < n;i++) {
		int x,y; cin >> x >> y;
		v[x].pb(y), v[y].pb(x);
	}
	for(int i = 1;i <= n;i++) {
		if(v[i].size() >= 2) root = i;
	}
	dfs(root,-1,1);
	dfs2(root,-1,root);
	dfs3(root,-1);
	build(1,1,n);
	while(Q--) {
		int cnt,x;
		int tans,tleaf;
		tans = ans, tleaf = leaf;
		cin >> cnt;
		vec q,rq;
		for(int i = 1;i <= cnt;i++) {
			cin >> x; q.pb(x);
			cn[x]++;
			tans++;
		}
		for(int i : q) {
			if(v[i].size() != 1) tleaf += cn[i], rq.pb(i);
			else {
				if(cn[i]) tleaf += cn[i]-1;
				if(cn[i]&&cn[i] % 2 == 0) rq.pb(i);
			}
			cn[i] = 0;
		}
		for(int i : rq) {
			pi tmp = queryLCA(i,root);
			tans += tmp.y-tmp.x;
		}
		if(tleaf % 2) cout << "-1\n";
		else cout << tans << '\n';
		for(int i : rq) queryLCA(i,root);
		for(int i : q) cn[i] = 0;
	}
}

Compilation message

cleaning.cpp:6: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    6 | #pragma gcc optimize("O3")
      | 
cleaning.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      | 
cleaning.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("unroll-loops")
      |

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 234 ms 5376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3696 KB Output is correct
2 Correct 12 ms 3716 KB Output is correct
3 Correct 50 ms 12132 KB Output is correct
4 Correct 67 ms 11108 KB Output is correct
5 Correct 88 ms 13160 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 4716 KB Output is correct
2 Correct 129 ms 4716 KB Output is correct
3 Correct 86 ms 20204 KB Output is correct
4 Correct 288 ms 19688 KB Output is correct
5 Correct 66 ms 18284 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 5484 KB Output is correct
2 Correct 80 ms 5100 KB Output is correct
3 Correct 13 ms 4972 KB Output is correct
4 Correct 14 ms 5356 KB Output is correct
5 Correct 20 ms 5508 KB Output is correct
6 Correct 111 ms 5612 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 9460 KB Output is correct
2 Correct 491 ms 10092 KB Output is correct
3 Correct 378 ms 6636 KB Output is correct
4 Correct 485 ms 10076 KB Output is correct
5 Correct 482 ms 10100 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 13676 KB Output is correct
2 Correct 216 ms 17388 KB Output is correct
3 Correct 325 ms 17208 KB Output is correct
4 Correct 303 ms 17644 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 234 ms 5376 KB Output is correct
3 Correct 12 ms 3696 KB Output is correct
4 Correct 12 ms 3716 KB Output is correct
5 Correct 50 ms 12132 KB Output is correct
6 Correct 67 ms 11108 KB Output is correct
7 Correct 88 ms 13160 KB Output is correct
8 Correct 132 ms 4716 KB Output is correct
9 Correct 129 ms 4716 KB Output is correct
10 Correct 86 ms 20204 KB Output is correct
11 Correct 288 ms 19688 KB Output is correct
12 Correct 66 ms 18284 KB Output is correct
13 Correct 158 ms 5484 KB Output is correct
14 Correct 80 ms 5100 KB Output is correct
15 Correct 13 ms 4972 KB Output is correct
16 Correct 14 ms 5356 KB Output is correct
17 Correct 20 ms 5508 KB Output is correct
18 Correct 111 ms 5612 KB Output is correct
19 Correct 298 ms 9460 KB Output is correct
20 Correct 491 ms 10092 KB Output is correct
21 Correct 378 ms 6636 KB Output is correct
22 Correct 485 ms 10076 KB Output is correct
23 Correct 482 ms 10100 KB Output is correct
24 Correct 422 ms 13676 KB Output is correct
25 Correct 216 ms 17388 KB Output is correct
26 Correct 325 ms 17208 KB Output is correct
27 Correct 303 ms 17644 KB Output is correct
28 Correct 343 ms 9836 KB Output is correct
29 Correct 290 ms 16620 KB Output is correct
30 Correct 90 ms 14568 KB Output is correct
31 Correct 302 ms 21272 KB Output is correct
32 Correct 518 ms 9964 KB Output is correct
33 Correct 308 ms 16128 KB Output is correct
34 Correct 341 ms 16364 KB Output is correct
35 Correct 373 ms 17328 KB Output is correct