Submission #1271347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271347		SoMotThanhXuan	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	121 ms	20844 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define Mask(i) (1 << (i))
#define Bit(x, i) (((x) >> (i)) & 1)
const int mod = 1e9 + 7;
int fastPow(int a, int n){
	if(n == 0) return 1;
	int t = fastPow(a, n >> 1);
	t = 1ll * t * t % mod;
	if(n & 1) t = 1ll * t * a % mod;
	return t;
}
bool minimize(int &u, int v) { return u > v ? u = v, true : false;}
bool maximize(int &u, int v) { return u < v ? u = v, true : false;}
bool minimizell(long long &u, long long v) { return u > v ? u = v, true : false;}
bool maximizell(long long &u, long long v) { return u < v ? u = v, true : false;}
const int maxN = 1e5 + 5;
int n, q;
vector<int> adj[maxN];
vector<int> query[maxN];
int numNode[maxN];
namespace subtask2{
	bool check(){
		return n <= 20000 && q <= 300;
	}
	const int maxN = 2e5 + 5;
	int orgN;
	long long answer = 0;
	int numLeaves[maxN];
	void dfs(int u, int p){
		numLeaves[u] = 0;
		if(u != 1){
			if(adj[u].size() == 1){
				numLeaves[u] = 1;
				return;
			}
		}
		for(int v : adj[u]){
			if(v == p) continue;
			dfs(v, u);
			answer += numLeaves[v];
			numLeaves[u] += numLeaves[v];
		}
		if(numLeaves[u] % 2 == 1)numLeaves[u] = 1;
		else numLeaves[u] = 2;
	}
	void solve(){
		orgN = n;
		FOR(i, 1, q) {
			n = orgN;
//			for(int u : query[i])cout << u << ' ';cout << '\n';
			for(int u : query[i]){
				adj[u].emplace_back(++n);
				adj[n].emplace_back(u);
			}
			int numLeaves = 0;
			FOR(i, 1, n){
				if(adj[i].size() == 1)++numLeaves;
			}
			if(numLeaves % 2 == 1){
				FOR(i, 1, orgN){
					while(!adj[i].empty() && adj[i].back() > orgN) adj[i].pop_back();
				}
				FOR(i, orgN + 1, n)adj[i].clear();
				cout << -1 << '\n';
				continue;
			}
			answer = 0;
			dfs(1, 0);
			cout << answer << '\n';
			FOR(i, 1, orgN){
				while(!adj[i].empty() && adj[i].back() > orgN) adj[i].pop_back();
			}
			FOR(i, orgN + 1, n)adj[i].clear();
		}
	}
}
namespace ac{
	int numLeaves[maxN];
	long long rem = 0;
	int chain[maxN], curChain = 1, top[maxN], arr[maxN], lab[maxN], curLab = 1, sz[maxN], par[maxN];
	void dfs(int u = 1, int p = 0){
		if(u != 1){
			if(adj[u].size() == 1){
				numLeaves[u] = 1;
				return;
			}
		}
		sz[u] = 1;
		for(int v : adj[u]){
			if(v == p) continue;
			par[v] = u;
			dfs(v, u);
			sz[u] += sz[v];
			numLeaves[u] += numLeaves[v];
			rem += numLeaves[v];
		}
		if(numLeaves[u] % 2 == 0)numLeaves[u] = 2;
		else numLeaves[u] = 1;
	}
	void hld(int u = 1, int p = 0){
		if(top[curChain] == 0) top[curChain] = u;
		chain[u] = curChain;
		lab[u] = curLab;
		arr[curLab] = u;
		++curLab;
		int h = 0;
		for(int v : adj[u]){
			if(v == p) continue;
			if(sz[v] > sz[h]) h = v;
		}
		if(h) hld(h, u);
		for(int v : adj[u]){
			if(v != h && v != p){
				++curChain;
				hld(v, u);
			}
		}
	}
	int it[maxN << 2], len[maxN << 2];
	int lz[maxN << 2];
	void push(int id){
		if(lz[id] == 0) return;
		FOR(x, id << 1, id << 1 | 1){
            lz[x] ^= 1;
            it[x] = len[x] - it[x];
		}
		lz[id] = 0;
		return;
	}
	void build(int id, int l, int r){
		if(l == r){
			int u = arr[l];
			len[id] = 1;
			if(numLeaves[u] == 2) it[id] = 1;
			return;
		}
		int mid = l + r >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
		it[id] = it[id << 1] + it[id << 1 | 1];
		len[id] = len[id << 1] + len[id << 1 | 1];
	}
	void update(int id, int l, int r, int u, int v){
		if(l > v || r < u) return;
		if(l >= u && r <= v){
			it[id] = len[id] - it[id];
			lz[id] ^= 1;
			return;
		}
		push(id);
		int mid = l + r >> 1;
		update(id << 1, l, mid, u, v);
		update(id << 1 | 1, mid + 1, r, u, v);
		it[id] = it[id << 1] + it[id << 1 | 1];
	}
	int get(int id, int l, int r, int u, int v){
		if(l >= u && r <= v) return it[id];
		int mid = l + r >> 1;
		push(id);
		if(v <= mid) return get(id << 1, l, mid, u, v);
		if(u > mid) return get(id << 1 | 1, mid + 1, r, u, v);
		return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
	}
	void change(int u){
		while(chain[u] != chain[1]){
			update(1, 1, n, lab[top[chain[u]]], lab[u]);
			u = par[top[chain[u]]];
		}
		if(u != 1) update(1, 1, n, lab[1] + 1, lab[u]);
	}
	int deg[maxN];
	int cnt[maxN];
	bool Leaves[maxN];
	void solve(){
	    FOR(i, 1, n)deg[i] = adj[i].size();
		int orgLeaves = 0;
		FOR(i, 1, n)if(deg[i] <= 1)++orgLeaves;
		FOR(i, 1, n)Leaves[i] = deg[i] <= 1;
		dfs();
		hld();
		numLeaves[1] = 0;
		build(1, 1, n);

//		cout << orgLeaves << '\n';
		FOR(i, 1, q){
			int curLeaves = orgLeaves;
			for(int u : query[i]){
				if(deg[u] <= 1)--curLeaves;
				++curLeaves;
				deg[u]++;
				cnt[u]++;
			}
			sort(all(query[i]));
			uni(query[i]);
			if(curLeaves % 2 == 1){
				cout << -1 << '\n';
				for(int u : query[i]){
					deg[u] = adj[u].size();
					cnt[u] = 0;
				}
				continue;
			}

			for(int u : query[i]){
                if(Leaves[u] && ((cnt[u] & 1) == 0))change(u);
                else if(!Leaves[u] && ((cnt[u] & 1) == 1)) change(u);
			}
			cout << n - 1 + numNode[i] + it[1] << '\n';
			for(int u : query[i]){
                if(Leaves[u] && ((cnt[u] & 1) == 0))change(u);
                else if(!Leaves[u] && ((cnt[u] & 1) == 1)) change(u);
			}
			for(int u : query[i]){
				deg[u] = adj[u].size();
				cnt[u] = 0;
			}
		}
	}
}
void process(){
	cin >> n >> q;
	FOR(i, 1, n - 1){
		int u, v;
		cin >> u >> v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	FOR(i, 1, q){
		cin >> numNode[i];
		query[i].resize(numNode[i]);
		for(int &u : query[i])cin >> u;
	}
	//if(subtask2 :: check()) return subtask2 :: solve();
	return ac :: solve();

}
//#define LOVE "crt"
int main(){
//	freopen(LOVE".inp", "r", stdin);
//	freopen(LOVE".out", "w", stdout);
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	process();
	return 0;
}

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