Submission #344761

#	Time	Username	Problem	Language	Result	Execution time	Memory
344761		hugo_pm	동기화 (JOI13_synchronization)	C++17	100 / 100	465 ms	30544 KiB

synchronization

#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
using ll = long long;

namespace sum32 {
    int op(int a, int b) { return a + b; }
    int e() { return 0; }
    using st = segtree<int, op, e>;
}

namespace min32 {
    int op(int a, int b) { return (a < b ? a : b); }
    int e() { return -((1<<30)-10); }
    using st = segtree<int, op, e>;
}

namespace max32 {
    int op(int a, int b) { return (a > b ? a : b); }
    int e() { return ((1<<30)-10); }
    using st = segtree<int, op, e>;
}

namespace sum64 {
    ll op(ll a, ll b) { return a + b; }
    ll e() { return 0; }
    using st = segtree<ll, op, e>;
}

namespace min64 {
    ll op(ll a, ll b) { return (a < b ? a : b); }
    ll e() { return -((1LL<<60)-10); }
    using st = segtree<ll, op, e>;
}

namespace max64 {
    ll op(ll a, ll b) { return (a > b ? a : b); }
    ll e() { return ((1LL<<60)-10); }
    using st = segtree<ll, op, e>;
}
// 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);
	sum32::st 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: 14:47:24
// Generated: 14:47:25

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40