oj.uz

Submission #344779

# Submission time Handle Problem Language Result Execution time Memory
344779 2021-01-06T14:18:22 Z hugo_pm Synchronization (JOI13_synchronization) C++17
100 / 100
 502 ms 31312 KB 
#include <bits/stdc++.h>
// Begin hl/core.hpp
#include <bits/stdc++.h>
using namespace std;

// Utilities

using ll = long long;
const int m197 = 1000000007;
const int m998 = 998244353;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)

template<typename T>
void chmax(T &x, const T &v) {
	if (x < v) {
		x = v;
	}
}

template<typename T>
void chmin(T &x, const T &v) {
	if (x > v) {
		x = v;
	}
}

template<typename T>
int len(const T &x) {
	return (int)(x.size());
}

// Debug

void dbg_out() {
	cout << endl;
}

template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
	cout << ' ' << H;
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type
operator<<(Ostream& os,  const Cont& v){
	os << "[";
	for (auto &x : v) {
		os << x << ", ";
	}
	return os << "]";
}

template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p) {
	return os << "{" << p.first << ", " << p.second << "}";
}

// Multi-dimensional vector

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
	static_assert(D >= 1, "Vector dimension must be greater than zero!");
	template<typename... Args>
		Vec(int n, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template<typename T>
struct Vec<1, T> : public vector<T> {
	Vec(int n, const T& val = T()) : vector<T>(n, val) {}
};

// Recursive lambda

template<class Fun>
class letrec_result {
	Fun fun_;
public:
	template<class T>
		explicit letrec_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
		decltype(auto) operator()(Args &&...args) {
			return fun_(ref(*this), std::forward<Args>(args)...);
		}
};

template<class Fun>
decltype(auto) letrec(Fun &&fun) {
	return letrec_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

// Input / Output

ll nxt() {
	ll x;
	cin >> x;
	return x;
}

template<typename T>
vector<T> read_vector(int n) {
	vector<T> v(n);
	for (T &x : v) {
		cin >> x;
	}
	return v;
}

template<typename T>
void print_vector(vector<T> data, bool print_size, bool new_line) {
	int n = data.size();
	if (print_size) {
		cout << n << '\n';
	}
	for (int i = 0; i < n; ++i) {
		cout << data[i] << " \n"[i+1 == n || new_line];
	}
}
// End hl/core.hpp
// Begin hl/data/usual.hpp
// Begin hl/data/segtree.hpp
#include <vector>

template<class node, node (*op)(node, node), node (*e)()>
class segtree {
public:
	segtree(std::vector<node> v) : _n(v.size()), log(0) {
		while ((1 << log) < _n) {
			++log;
		}

		size = (1 << log);
		data.assign(2*size, e());

		for (int i = 0; i < _n; ++i) {
			data[size+i] = v[i];
		}

		for (int i = size-1; i >= 1; --i) {
			update(i);
		}
	}

	segtree(int t = 0, node x = e()) : segtree(std::vector<node>(t, x)) { }

	node get(int pos) {
		return data[size+pos];
	}

	void set(int pos, node val) {
		pos += size;
		data[pos] = val;
		for (int i = 1; i <= log; ++i) {
			update(pos >> i);
		}
	}

	void refresh(int pos, node proposal) {
		set(pos, op(data[size+pos], proposal));
	}

	node query_semi_open(int left, int right) {
		left += size;
		right += size;
		node res_left = e(), res_right = e(); 

		while (left < right) {
			if (left & 1) {
				res_left = op(res_left, data[left++]);
			}
			if (right & 1) {
				res_right = op(data[--right], res_right);
			}
			left >>= 1, right >>= 1;	
		}

		return op(res_left, res_right);
	}

	node query_all() {
		return data[1];
	}

private:
	int _n, log, size;
	std::vector<node> data;

	void update(int k) {
		data[k] = op(data[k<<1], data[k<<1|1]);
	}
};
// End hl/data/segtree.hpp
// Begin hl/data/lazy_segtree.hpp
#include <vector>
#include <cassert>

template<class node,
node (*op)(node, node),
node (*e)(),
class fun,
node (*eval)(fun, node),
fun (*composition)(fun, fun),
fun (*id)()>
class lazy_segtree {
public:
	lazy_segtree(std::vector<node> v) : _n(v.size()), log(0) {
		while ((1 << log) < _n) {
			++log;
		}

		size = (1 << log);
		data.assign(2*size, e());
		lazy.assign(size, id());

		for (int i = 0; i < _n; ++i) {
			data[size + i] = v[i];
		}

		for (int i = size-1; i >= 1; --i) {
			update_one(i);
		}
	}

	lazy_segtree(int t = 0, node x = e()) : lazy_segtree(std::vector<node>(t, x)) { }

	node get(int pos) {
		int leaf = pos + size;
		push_anc(leaf);
		return data[leaf];
	}

	void set(int pos, node val) {
		int leaf = pos + size;
		push_anc(leaf);
		data[leaf] = val;
		update_anc(leaf);
	}

	node query_semi_open(int left, int right) {
		left += size;
		right += size;
		node res_left = e(), res_right = e();

		push_anc(left, left);
		push_anc(right, right);

		while (left < right) {
			if (left & 1) {
				res_left = op(res_left, data[left++]);
			}
			if (right & 1) {
				res_right = op(data[--right], res_right);
			}
			left >>= 1;
			right >>= 1;	
		}

		return op(res_left, res_right);
	}

	node query_all() {
		return data[1];
	}

	void apply_one(int pos, fun fct) {
		int leaf = pos + size;
		push_anc(leaf);
		data[leaf] = eval(fct, data[leaf]);
		update_anc(leaf);
	}

	void apply_semi_open(int left, int right, fun fct) {
		left += size;
		right += size;

		if (left == right) {
			return;
		}

		push_anc(left, left);
		push_anc(right - 1, right);

		int old_left = left, old_right = right;
		while (left < right) {
			if (left & 1) {
				all_apply(left++, fct);
			}
			if (right & 1) {
				all_apply(--right, fct);
			}
			left >>= 1;
			right >>= 1;
		}

		left = old_left, right = old_right;
		update_anc(left, left);
		update_anc(right - 1, right);
	}

private:
	int _n, log, size;
	std::vector<node> data;
	std::vector<fun> lazy;

	void update_one(int k) {
		data[k] = op(data[k << 1], data[k << 1 | 1]);
	}

	void update_anc(int leaf, int dev = 1) {
		int s = 1 + __builtin_ctz(dev);
		for (int i = s; i <= log; ++i) {
			update_one(leaf >> i);
		}
	}

	void all_apply(int k, fun fct) {
		data[k] = eval(fct, data[k]);
		if (k < size) {
			lazy[k] = composition(fct, lazy[k]);
		}
	}

	void push_one(int k) {
		all_apply(k << 1, lazy[k]);
		all_apply(k << 1 | 1, lazy[k]);
		lazy[k] = id();
	}

	void push_anc(int leaf, int dev = 1) {
		int s = 1 + __builtin_ctz(dev);
		for (int i = log; i >= s; --i) {
			push_one(leaf >> i);
		}
	}
};
// End hl/data/lazy_segtree.hpp
#include <optional>
using ll = long long;

template<typename T, const T BIG_>
struct numeric_segtree {
	static constexpr T BIG = BIG_;
	static T fct_sum(T a, T b) { return a + b; }
	static T e_sum() { return 0; }

	static T fct_min(T a, T b) { return (a < b ? a : b); }
	static T e_min() { return BIG; }

	static T fct_max(T a, T b) { return (a > b ? a : b); }
	static T e_max() { return -BIG; }

	using segtree_min = segtree<T, fct_min, e_min>;
	using segtree_max = segtree<T, fct_max, e_max>;
	using segtree_sum = segtree<T, fct_sum, e_sum>;

	using lazy_min_add = lazy_segtree<T, fct_min, e_min, T, fct_sum, fct_sum, e_sum>;
	using lazy_max_add = lazy_segtree<T, fct_max, e_max, T, fct_sum, fct_sum, e_sum>;
	using lazy_sum_add = lazy_segtree<T, fct_sum, e_sum, T, fct_sum, fct_sum, e_sum>;

	using set_struct = std::optional<T>;
	static set_struct comp_set(set_struct f1, set_struct f2) {
		return (f1 ? f1 : f2);
	}
	static T eval_set(set_struct fct, T val) {
		return (fct ? *fct : val);
	}
	static set_struct e_set() {
		return std::nullopt;
	}

	using lazy_min_set = lazy_segtree<T, fct_min, e_min, set_struct, eval_set, comp_set, e_set>;
};

using usual32 = numeric_segtree<int, (int)1e9>;
using usual64 = numeric_segtree<long long, (ll)3e18>;

// End hl/data/usual.hpp

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int nb_node = nxt(), nb_switch = nxt(), nb_query = nxt();
	Vec<2, int> adj(nb_node, 0);
	vector<pair<int, int>> orig;
	rep(id_edge, 0, nb_node - 1) {
		int u = nxt() - 1, v = nxt() - 1;
		adj[u].push_back(v);
		adj[v].push_back(u);
		orig.emplace_back(u, v);
	}
	const int ROOT = 0;
	int nb_level = __lg(nb_node) + 1;
	Vec<2, int> anc(nb_node, nb_level, -1);
	vector<int> tin(nb_node), tout(nb_node);
	int timer = 0;

	auto build = letrec([&] (auto self, int node) -> void {
		tin[node] = timer++;
		rep(l, 1, nb_level) {
			int t = anc[node][l-1];
			if (t == -1) break;
			anc[node][l] = anc[t][l-1];
		}
		for (int child : adj[node]) if (child != anc[node][0]) {
			anc[child][0] = node;
			self(child);
		}
		tout[node] = timer++;
	});

	build(ROOT);
	vector<bool> active(nb_node, false);
	usual32::segtree_sum rsum(timer+1, 0);

	auto find_root = [&] (int node) {
		for (int level = nb_level-1; level >= 0; --level) {
			int jto = anc[node][level];
			if (jto == -1) continue;
			int nb_active = rsum.query_semi_open(tin[jto] + 1, tin[node] + 1);
			if (nb_active == 1<<level) {
				node = jto;
			}
		}
		return node;
	};

	auto upd = [&] (int node, int x) {
		rsum.set(tin[node], x);
		rsum.set(tout[node], -x); 
		active[node] = x;
	};

	vector<int> info(nb_node, 1), last_sync(nb_node, 0);

	rep(id_switch, 0, nb_switch) {
		auto [par, low] = orig[nxt()-1];
		if (low == anc[par][0]) swap(par, low);
		if (active[low]) {
			info[low] = last_sync[low] = info[find_root(low)];
			upd(low, 0);
		} else {
			upd(low, 1);
			info[find_root(low)] += info[low] - last_sync[low];
		}
	}

	rep(id_query, 0, nb_query) {
		cout << info[find_root(nxt() - 1)] << "\n";
	}
}
// File: /home/hugo/Algo/sync/main.cpp
// Last touch: 15:17:39
// Generated: 15:17:45

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 19 ms 2412 KB Output is correct
8 Correct 17 ms 2412 KB Output is correct
9 Correct 23 ms 2560 KB Output is correct
10 Correct 384 ms 22480 KB Output is correct
11 Correct 391 ms 22808 KB Output is correct
12 Correct 408 ms 30604 KB Output is correct
13 Correct 199 ms 22604 KB Output is correct
14 Correct 233 ms 22096 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 26580 KB Output is correct
2 Correct 136 ms 26204 KB Output is correct
3 Correct 171 ms 30080 KB Output is correct
4 Correct 166 ms 29924 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 30 ms 3308 KB Output is correct
8 Correct 470 ms 31184 KB Output is correct
9 Correct 502 ms 31228 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 31312 KB Output is correct
2 Correct 250 ms 30808 KB Output is correct
3 Correct 251 ms 31056 KB Output is correct
4 Correct 271 ms 31144 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 25 ms 2540 KB Output is correct
7 Correct 466 ms 23888 KB Output is correct
8 Correct 469 ms 31312 KB Output is correct
9 Correct 236 ms 23892 KB Output is correct
10 Correct 277 ms 23504 KB Output is correct
11 Correct 190 ms 27984 KB Output is correct
12 Correct 190 ms 27728 KB Output is correct
13 Correct 259 ms 31184 KB Output is correct