oj.uz

답안 #344761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344761 2021-01-06T13:48:05 Z hugo_pm 동기화 (JOI13_synchronization) C++17
100 / 100
 465 ms 30544 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
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.0 / 10.0

# 결과 실행 시간 메모리 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 2 ms 492 KB Output is correct
7 Correct 18 ms 2412 KB Output is correct
8 Correct 17 ms 2412 KB Output is correct
9 Correct 17 ms 2412 KB Output is correct
10 Correct 337 ms 22096 KB Output is correct
11 Correct 340 ms 22096 KB Output is correct
12 Correct 385 ms 29832 KB Output is correct
13 Correct 194 ms 22348 KB Output is correct
14 Correct 224 ms 21968 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 26064 KB Output is correct
2 Correct 135 ms 25820 KB Output is correct
3 Correct 166 ms 29776 KB Output is correct
4 Correct 168 ms 29904 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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 2 ms 620 KB Output is correct
7 Correct 27 ms 3308 KB Output is correct
8 Correct 455 ms 29960 KB Output is correct
9 Correct 465 ms 30000 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 462 ms 30032 KB Output is correct
2 Correct 251 ms 30456 KB Output is correct
3 Correct 249 ms 30544 KB Output is correct
4 Correct 257 ms 30396 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 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 2 ms 492 KB Output is correct
6 Correct 25 ms 2540 KB Output is correct
7 Correct 416 ms 22480 KB Output is correct
8 Correct 458 ms 30032 KB Output is correct
9 Correct 219 ms 22860 KB Output is correct
10 Correct 265 ms 22864 KB Output is correct
11 Correct 191 ms 26704 KB Output is correct
12 Correct 185 ms 26704 KB Output is correct
13 Correct 258 ms 30416 KB Output is correct