oj.uz

Submission #344745

# Submission time Handle Problem Language Result Execution time Memory
344745 2021-01-06T13:17:02 Z hugo_pm Synchronization (JOI13_synchronization) C++17
100 / 100
 835 ms 31548 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

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

namespace sum64 {
    long long op(long long a, long long b) { return a + b; }
    long long e() { return 0LL; }
    using st = segtree<long long, op, e>;
}// End hl/data/usual.hpp

int main() {
	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:16:05
// Generated: 14:16:29

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 364 KB Output is correct
3 Correct 1 ms 256 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 25 ms 2412 KB Output is correct
8 Correct 24 ms 2412 KB Output is correct
9 Correct 25 ms 2412 KB Output is correct
10 Correct 461 ms 22908 KB Output is correct
11 Correct 436 ms 23124 KB Output is correct
12 Correct 454 ms 30544 KB Output is correct
13 Correct 269 ms 22728 KB Output is correct
14 Correct 289 ms 22244 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 26576 KB Output is correct
2 Correct 207 ms 26204 KB Output is correct
3 Correct 221 ms 29904 KB Output is correct
4 Correct 223 ms 29904 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 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 620 KB Output is correct
7 Correct 58 ms 3308 KB Output is correct
8 Correct 799 ms 31344 KB Output is correct
9 Correct 835 ms 31548 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 31440 KB Output is correct
2 Correct 582 ms 30988 KB Output is correct
3 Correct 574 ms 31332 KB Output is correct
4 Correct 570 ms 31184 KB Output is correct

Subtask #5
40.0 / 40.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 5 ms 492 KB Output is correct
6 Correct 56 ms 2540 KB Output is correct
7 Correct 766 ms 23760 KB Output is correct
8 Correct 784 ms 31404 KB Output is correct
9 Correct 562 ms 23928 KB Output is correct
10 Correct 583 ms 23524 KB Output is correct
11 Correct 517 ms 27816 KB Output is correct
12 Correct 532 ms 27808 KB Output is correct
13 Correct 573 ms 31176 KB Output is correct