oj.uz

Submission #404942

# Submission time Handle Problem Language Result Execution time Memory
404942 2021-05-15T10:42:19 Z silverfish Spring cleaning (CEOI20_cleaning) C++14
53 / 100
 1000 ms 21820 KB 
#include <bits/stdc++.h>
using namespace std;

/*<DEBUG>*/
#define tem template <typename 
#define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i)
#define _op debug& operator<<
tem C > auto test(C *x) -> decltype(cerr << *x, 0LL);
tem C > char test(...);
tem C > struct itr{C begin, end; };
tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; }
struct debug{
#ifdef _LOCAL
	~debug(){ cerr << endl; }
	tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; }
	tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); }
	tem T, typename U > _op (pair<T, U> i){ 
		return *this << "< " << i.first << " , " << i.second << " >"; }
	tem T> _op (itr<T> i){
		*this <<  "{ ";
		for(auto it = i.begin; it != i.end; it++){
			*this << " , " + (it==i.begin?2:0) << *it;
		}
		return *this << " }";
	}
#else
tem T> _op (const T&) { return *this; }
#endif 
};

tem T>
string _ARR_(T* arr, int sz){
	string ret = "{ " + to_string(arr[0]); 
	for(int i = 1; i < sz; i++) ret += " , " +  to_string(arr[i]);
	ret += " }"; return ret;
}

#define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]"
/*</DEBUG>*/

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
typedef pair<int, int> pii;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define TC int __TC__; cin >> __TC__; while(__TC__--)
#define ar array

const int INF = 1e9 + 7, N = 2e5 + 10;

vector<int> adj[N];
int win[N], wout[N], in[N], out[N], add[N];
int ans = 0, n, q, d, cur,fst=0, leafs = 0, par[N], nin, nout;
bool was_leaf[N], leaf[N];

void dfs(int u, int p=fst){
	par[u] = p;
	in[u] = out[u] = 0;
	for(int v : adj[u]){
		if(v != p){
			dfs(v, u);
			in[u] += out[v];
		}
	}


	if(adj[u].size() == 1){
		in[u] = 0;
		out[u] = 1;
		++leafs;
		leaf[u] = 1;
	}else{
		out[u] = (in[u]%2 ? 1 : 2);
	}

	ans += in[u];
	win[u] = in[u];
	wout[u] = out[u];
	return;
}

void solve_subtask5();

int main()
{
	FAST;
	cin >> n >> q;
	for(int i = 0; i < n-1; ++i){
		int u, v; cin >> u >> v;
		--u; --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}


	for(int i = 0; i < n; ++i){
		if(adj[fst].size() == 1 && adj[i].size() != 1) fst = i;

	}

	if((n > 20000 && q > 1) || q > 300){
		solve_subtask5();
		return 0;
	}


	cur = n-1;
	while(q--){
		cin >> d;
		leafs=0;
		ans = 0;
 
		for(int i = 0; i < d; ++i){
			cin >> add[i];
			--add[i];
			++cur;
			adj[add[i]].pb(cur);
			adj[cur].pb(add[i]);
		}
 
		ans = 0;
		dfs(fst);
		cout << (leafs%2 ? -1 : ans) << '\n';
 
		for(int i = 0; i < d; ++i){
			adj[add[i]].pop_back();
		}
 
		for(; cur >= n; --cur){
			adj[cur].pop_back();
		}
	}


	return 0;
}

void solve_subtask5(){
	dfs(fst);

	while(q--){
		cur = n-1;
		cin >> d;

		for(int i = 0; i < d; ++i){
			++cur;
			cin >> add[i];
			--add[i];
			if(leaf[add[i]]){
				was_leaf[i] = 1;
				leaf[add[i]] = 0;
				--leafs;
			}
			++leafs;

			adj[add[i]].pb(cur);
			in[cur] = 0;
			out[cur] = 1;

			int u = add[i];

			while(1){
				ans -= in[u];
				in[u] = out[u] = 0;
				for(int v : adj[u]){
					if(v != par[u]){
						in[u] += out[v];
					}
				}

				out[u] = (in[u]%2 ? 1 : 2);
				ans += in[u];
				if(u == fst) break;
				u = par[u];
			}
		}

		cout << (leafs%2 ? -1 : ans) << '\n';

		for(int i = 0; i < d; ++i){
			adj[add[i]].pop_back();
			if(was_leaf[i]){
				leafs++;
				leaf[add[i]] = 1;
				was_leaf[i] = 0;
			} 
			leafs--;

			int u = add[i];
			while(1){
				ans += win[u] - in[u];
				in[u] = win[u];
				out[u] = wout[u];
				if(u == fst) break;
				u = par[u];
			}
		}

	}
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 97 ms 6344 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10084 KB Output is correct
2 Correct 28 ms 10076 KB Output is correct
3 Correct 42 ms 10836 KB Output is correct
4 Correct 73 ms 13884 KB Output is correct
5 Correct 92 ms 15548 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10556 KB Output is correct
2 Correct 31 ms 10572 KB Output is correct
3 Correct 57 ms 17816 KB Output is correct
4 Correct 101 ms 21820 KB Output is correct
5 Correct 47 ms 16644 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 6816 KB Output is correct
2 Correct 198 ms 6352 KB Output is correct
3 Correct 262 ms 6092 KB Output is correct
4 Correct 304 ms 6680 KB Output is correct
5 Correct 260 ms 6792 KB Output is correct
6 Correct 307 ms 6724 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 8644 KB Output is correct
2 Correct 122 ms 8620 KB Output is correct
3 Correct 81 ms 6920 KB Output is correct
4 Correct 116 ms 8516 KB Output is correct
5 Correct 122 ms 8532 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 11072 KB Output is correct
2 Execution timed out 1089 ms 12996 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 97 ms 6344 KB Output is correct
3 Correct 29 ms 10084 KB Output is correct
4 Correct 28 ms 10076 KB Output is correct
5 Correct 42 ms 10836 KB Output is correct
6 Correct 73 ms 13884 KB Output is correct
7 Correct 92 ms 15548 KB Output is correct
8 Correct 31 ms 10556 KB Output is correct
9 Correct 31 ms 10572 KB Output is correct
10 Correct 57 ms 17816 KB Output is correct
11 Correct 101 ms 21820 KB Output is correct
12 Correct 47 ms 16644 KB Output is correct
13 Correct 281 ms 6816 KB Output is correct
14 Correct 198 ms 6352 KB Output is correct
15 Correct 262 ms 6092 KB Output is correct
16 Correct 304 ms 6680 KB Output is correct
17 Correct 260 ms 6792 KB Output is correct
18 Correct 307 ms 6724 KB Output is correct
19 Correct 79 ms 8644 KB Output is correct
20 Correct 122 ms 8620 KB Output is correct
21 Correct 81 ms 6920 KB Output is correct
22 Correct 116 ms 8516 KB Output is correct
23 Correct 122 ms 8532 KB Output is correct
24 Correct 224 ms 11072 KB Output is correct
25 Execution timed out 1089 ms 12996 KB Time limit exceeded
26 Halted 0 ms 0 KB -