Submission #878783

#	Time	Username	Problem	Language	Result	Execution time	Memory
878783		phoenix0423	Spring cleaning (CEOI20_cleaning)	C++17	37 / 100	1059 ms	40276 KiB

cleaning

#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 (stderr)

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

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30