Submission #1123820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123820		Haikm13579	Spring cleaning (CEOI20_cleaning)	C++17	16 / 100	263 ms	16196 KiB

cleaning

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define pir pair<int,int>
using namespace std;
const int maxn = 2e5 + 5;

template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}

vector <int> Q[maxn],vec[maxn];

void input(int n,int q){
	for (int i = 1 ; i < n ; i++){
		int u,v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	
	for (int id = 1 ; id <= q ; id++){
		int len;
		cin >> len;
		Q[id].resize(len);
		
		for (int i = 0 ; i < len ; i++) cin >> Q[id][i];
	}
}

namespace subtask3{
	bool subtask3(int n,int q){
		return (n <= 20000 && q <= 300);
	}
	
	int XOR[maxn];
	
	int get_root(int n){
		for (int i = 1 ; i <= n ; i++)
		    if (vec[i].size() > 1) return i;
		
		return 1;
	}
	bool get_parity(int n){
		bool c = 0;
		for (int i = 1 ; i <= n ; i++)
		    c ^= (vec[i].size() == 1);
		return c;
	}
	
	int dfs(int u,int par){
		XOR[u] = 0;
		
		if (vec[u].size() <= 1){
			XOR[u] = 1;
			return 1;
		}
		
		int res = 0;
		for (int v : vec[u])
		    if (v != par){
		    	res += dfs(v,u);
		    	XOR[u] ^= XOR[v];
			}
		
		if (XOR[u]) res++;
		if (!XOR[u] && par > 0) res += 2;
		return res;
	}
	
	int get_answer(int root,int parity,int id,int n){
		int N = n;
		for (int u : Q[id])
		   vec[u].push_back(++N);
		
	    int res = dfs(root,0);
	    
		for (int u : Q[id])
		    while (vec[u].back() > n) vec[u].pop_back();
	    
	    if (XOR[root]) return -1;
		
		return res;
	}
	
	void solve(int n,int q){
		int root = get_root(n),parity = get_parity(n);
		
		for (int id = 1 ; id <= q ; id++)
		   cout << get_answer(root,parity,id,n) << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,q;
	cin >> n >> q;
	input(n,q);
	
	if (subtask3::subtask3(n,q)){
		subtask3::solve(n,q);
		return 0;
	}

	return 0;
}

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