oj.uz

Submission #878782

# Submission time Handle Problem Language Result Execution time Memory
878782 2023-11-25T08:22:45 Z phoenix0423 Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 1000 ms 21332 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;
		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){
	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(pos != rt){
		apply(loc[head[pos]], loc[pos]);
		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();
	for(int i = 0; i < q; i++){
		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<<qry(1, n - 1) + d<<"\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]);
		}
	}
	auto ed = clock();
	// cout<<float(ed - st) / CLOCKS_PER_SEC;
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:141:7: warning: unused variable 'ed' [-Wunused-variable]
  141 |  auto ed = clock();
      |       ^~

Subtask #1
0.0 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 10076 KB Output is correct
2 Correct 29 ms 10112 KB Output is correct
3 Correct 21 ms 13524 KB Output is correct
4 Correct 36 ms 13012 KB Output is correct
5 Correct 41 ms 14288 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10580 KB Output is correct
2 Correct 34 ms 10584 KB Output is correct
3 Correct 32 ms 21332 KB Output is correct
4 Correct 95 ms 21076 KB Output is correct
5 Correct 28 ms 20284 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 12968 KB Output is correct
2 Correct 140 ms 12628 KB Output is correct
3 Correct 124 ms 11608 KB Output is correct
4 Correct 137 ms 12624 KB Output is correct
5 Correct 136 ms 12728 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 15008 KB Output is correct
2 Execution timed out 1048 ms 16476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 167 ms 10844 KB Output is correct
3 Correct 28 ms 10076 KB Output is correct
4 Correct 29 ms 10112 KB Output is correct
5 Correct 21 ms 13524 KB Output is correct
6 Correct 36 ms 13012 KB Output is correct
7 Correct 41 ms 14288 KB Output is correct
8 Correct 46 ms 10580 KB Output is correct
9 Correct 34 ms 10584 KB Output is correct
10 Correct 32 ms 21332 KB Output is correct
11 Correct 95 ms 21076 KB Output is correct
12 Correct 28 ms 20284 KB Output is correct
13 Execution timed out 1071 ms 11148 KB Time limit exceeded
14 Halted 0 ms 0 KB -