oj.uz

Submission #878803

# Submission time Handle Problem Language Result Execution time Memory
878803 2023-11-25T08:51:44 Z phoenix0423 Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 1000 ms 40276 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int long long
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 0, n + 1)
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define pf push_front
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int N = 1e9 + 7;
const int INF = 1e9 + 7;
const int maxn = 1e5 + 5;
vector<int> adj[maxn];
int dep[maxn], par[maxn], head[maxn], siz[maxn], loc[maxn], id[maxn], dfn = 0;
int leaf[maxn], isleaf[maxn], used[maxn];
int n, q, rt, lfcnt = 0;
int ans = 0;

void dfs(int pos, int prev){
	if(prev != -1) adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), prev));
	siz[pos] = 1;
	for(auto &x : adj[pos]){
		par[x] = pos;
		dep[x] = dep[pos] + 1;
		siz[x] += siz[pos];
		dfs(x, pos);
		leaf[pos] += leaf[x];	
		if(siz[x] > siz[adj[pos][0]]) swap(x, adj[pos][0]);
	}
	if(!adj[pos].size()) isleaf[pos] = leaf[pos] = 1, lfcnt++;
}

void decompose(int pos, int h){
	id[dfn] = pos, loc[pos] = dfn++;
	head[pos] = h;
	for(auto x : adj[pos]){
		if(x == adj[pos][0]) decompose(x, h);
		else decompose(x, x);
	}
}

int st[maxn * 4], tag[maxn * 4];
void build(int v = 1, int l = 0, int r = n - 1){
	if(l == r){
		st[v] = 1 + (leaf[id[l]] - 1) % 2;
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m + 1, r);
	st[v] = st[v * 2] + st[v * 2 + 1];
}
void flip(int v, int l, int r){
	// cout<<"flip : "<<l<<" "<<r<<"\n";
	tag[v] ^= 1;
	st[v] = 3 * (r - l + 1) - st[v];
}
void push(int v, int l, int r){
	if(tag[v]){
		int m = (l + r) / 2;
		flip(v * 2, l, m);
		flip(v * 2 + 1, m + 1, r);
		tag[v] = 0;
	}
}
void apply(int l, int r, int v = 1, int L = 0, int R = n - 1){
	if(l > R || r < L) return;
	if(l <= L && r >= R){
		flip(v, L, R);
		return;
	}
	push(v, L, R);
	int m = (L + R) / 2;
	apply(l, r, v * 2, L, m);
	apply(l, r, v * 2 + 1, m + 1, R);
	st[v] = st[v * 2] + st[v * 2 + 1];
}
int qry(int l, int r, int v = 1, int L = 0, int R = n - 1){
	if(l > R || r < L) return 0;
	if(l <= L && r >= R) return st[v];
	push(v, L, R);
	int m = (L + R) / 2;
	return qry(l, r, v * 2, L, m) + qry(l, r, v * 2 + 1, m + 1, R);
}
void op(int pos){
	while(true){
		apply(loc[head[pos]], loc[pos]);
		if(head[pos] == rt) break;
		pos = par[head[pos]];
	}
}
void init(){
	dfs(rt, -1);
	decompose(rt, rt);
	build();
}

int main(void){
	fastio;
	cin>>n>>q;
	for(int i = 0; i < n - 1; i++){
		int a, b;
		cin>>a>>b;
		a--, b--;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for(int i = 0; i < n; i++){
		if(adj[i].size() > 1){
			rt = i;
			par[i] = i;
			break;
		}
	}	
	init();
	while(q--){
		int d;
		cin>>d;
		vector<int> a(d);
		for(int i = 0; i < d; i++){
			cin>>a[i];
			a[i] --;
			if(isleaf[a[i]] && !used[a[i]]) used[a[i]] = i + 1, lfcnt--;
			else op(a[i]);
		}
		if((lfcnt + d) % 2) cout<<-1<<"\n";
		else cout<<st[1] + d - 2<<"\n";
		for(int i = 0; i < d; i++){
			if(isleaf[a[i]] && used[a[i]] == i + 1) used[a[i]] = 0, lfcnt++;
			else op(a[i]);
		}
	}
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9052 KB Output is correct
2 Correct 170 ms 10200 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9560 KB Output is correct
2 Correct 40 ms 9564 KB Output is correct
3 Correct 22 ms 12752 KB Output is correct
4 Correct 47 ms 11988 KB Output is correct
5 Correct 46 ms 13012 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 11096 KB Output is correct
2 Correct 32 ms 11100 KB Output is correct
3 Correct 49 ms 40276 KB Output is correct
4 Correct 131 ms 37920 KB Output is correct
5 Correct 44 ms 37460 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 11336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 11540 KB Output is correct
2 Correct 147 ms 11472 KB Output is correct
3 Correct 114 ms 10480 KB Output is correct
4 Correct 158 ms 11452 KB Output is correct
5 Correct 148 ms 11484 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12884 KB Output is correct
2 Execution timed out 1072 ms 17244 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9052 KB Output is correct
2 Correct 170 ms 10200 KB Output is correct
3 Correct 39 ms 9560 KB Output is correct
4 Correct 40 ms 9564 KB Output is correct
5 Correct 22 ms 12752 KB Output is correct
6 Correct 47 ms 11988 KB Output is correct
7 Correct 46 ms 13012 KB Output is correct
8 Correct 57 ms 11096 KB Output is correct
9 Correct 32 ms 11100 KB Output is correct
10 Correct 49 ms 40276 KB Output is correct
11 Correct 131 ms 37920 KB Output is correct
12 Correct 44 ms 37460 KB Output is correct
13 Execution timed out 1032 ms 11336 KB Time limit exceeded
14 Halted 0 ms 0 KB -