Submission #829181

#	Time	Username	Problem	Language	Result	Execution time	Memory
829181		tranxuanbach	Werewolf (IOI18_werewolf)	C++17	100 / 100	853 ms	169740 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

#define isz(a) ((signed)a.size())

constexpr int N = 2e5 + 5, M = 4e5 + 5, Q = 2e5 + 5;
constexpr int NODE = 4e5 + 5;
constexpr int inf = 1e9 + 7;

struct merge_sort_tree{
	vector <int> seg[1 << 20];

	void build(int id, int l, int r, int a[]){
		if (l == r){
			seg[id].emplace_back(a[l]);
			return;
		}
		int mid = (l + r) >> 1;
		build(id * 2, l, mid, a);
		build(id * 2 + 1, mid + 1, r, a);
		merge(seg[id * 2].begin(), seg[id * 2].end(), seg[id * 2 + 1].begin(), seg[id * 2 + 1].end(), back_inserter(seg[id]));
	}

	int query(int id, int l, int r, int u, int v, int val){
		if (v < l or r < u){
			return inf;
		}
		if (u <= l and r <= v){
			auto itr = lower_bound(seg[id].begin(), seg[id].end(), val);
			return itr == seg[id].end() ? inf : *itr;
		}
		int mid = (l + r) >> 1;
		return min(query(id * 2, l, mid, u, v, val), query(id * 2 + 1, mid + 1, r, u, v, val));
	}
} seg;

struct Disjoint_set{
	int par[N];

	void reset(int sz = N){
		fill(par, par + sz, -1);
	}

	Disjoint_set(){
		reset();
	}

	int root(int x){
		return par[x] < 0 ? x : (par[x] = root(par[x]));
	}

	bool share(int x, int y){
		return root(x) == root(y);
	}

	bool merge(int x, int y){
		if ((x = root(x)) == (y = root(y))){
			return false;
		}
		if (par[x] > par[y]){
			swap(x, y);
		}
		par[x] += par[y];
		par[y] = x;
		return true;
	}
};

struct Query{
	int s, t, l, r;
};

int n, m, q;
vector <int> adj[N];
Query query[Q];

vector <int> adj_werewolf[NODE], adj_human[NODE];
int root_werewolf, root_human;
int node_werewolf[Q], node_human[Q];

int ctrtour, tour[NODE], tin[NODE], tout[NODE];

void dfs_tour(vector <int> adj[], int u){
	tour[ctrtour] = u;
	tin[u] = ctrtour;
	ctrtour++;
	for (auto v: adj[u]){
		dfs_tour(adj, v);
	}
	tout[u] = ctrtour;
}

pair <int, int> tour_range_werewolf[Q], tour_range_human[Q];
int pos_human[N], pos_werewolf[N];
int pos[NODE];
int ans[Q];

vector <int> check_validity(int _n, vector <int> _u, vector <int> _v, vector <int> _s, vector <int> _e, vector <int> _l, vector <int> _r){
	n = _n;
	m = isz(_u);
	for (int i = 0; i < m; i++){
		int u = _u[i], v = _v[i];
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	q = isz(_s);
	for (int i = 0; i < q; i++){
		int s = _s[i], t = _e[i], l = _l[i], r = _r[i];
		query[i] = Query{s, t, l, r};
	}

	{ // Human
		vector <pair <int, int>> query_human;
		for (int i = 0; i < q; i++){
			query_human.emplace_back(query[i].l, i);
		}
		sort(query_human.begin(), query_human.end());

		Disjoint_set dsu;
		vector <int> current_node(n);
		iota(current_node.begin(), current_node.end(), 0);
		root_human = n;

		for (int u = n - 1; u >= 0; u--){
			for (auto v: adj[u]){
				if (v < u){
					continue;
				}
				if (not dsu.share(u, v)){
					int x = current_node[dsu.root(u)], y = current_node[dsu.root(v)];
					dsu.merge(u, v);
					adj_human[root_human].emplace_back(x);
					adj_human[root_human].emplace_back(y);
					current_node[dsu.root(u)] = root_human;
					root_human++;
				}
			}
			while (not query_human.empty() and query_human.back().first == u){
				int i = query_human.back().second;
				node_human[i] = current_node[dsu.root(query[i].s)];
				query_human.pop_back();
			}
		}
		ctrtour = 0;
		dfs_tour(adj_human, root_human - 1);
		for (int i = 0; i < q; i++){
			tour_range_human[i] = pair{tin[node_human[i]], tout[node_human[i]]};
		}
		for (int u = 0; u < n; u++){
			pos_human[u] = tin[u];
		}
	}
	{ // Werewolf
		vector <pair <int, int>> query_werewolf;
		for (int i = 0; i < q; i++){
			query_werewolf.emplace_back(query[i].r, i);
		}
		sort(query_werewolf.begin(), query_werewolf.end(), greater <>());

		Disjoint_set dsu;
		vector <int> current_node(n);
		iota(current_node.begin(), current_node.end(), 0);
		root_werewolf = n;

		for (int u = 0; u < n; u++){
			for (auto v: adj[u]){
				if (v > u){
					continue;
				}
				if (not dsu.share(u, v)){
					int x = current_node[dsu.root(u)], y = current_node[dsu.root(v)];
					dsu.merge(u, v);
					adj_werewolf[root_werewolf].emplace_back(x);
					adj_werewolf[root_werewolf].emplace_back(y);
					current_node[dsu.root(u)] = root_werewolf;
					root_werewolf++;
				}
			}
			while (not query_werewolf.empty() and query_werewolf.back().first == u){
				int i = query_werewolf.back().second;
				node_werewolf[i] = current_node[dsu.root(query[i].t)];
				query_werewolf.pop_back();
			}
		}
		ctrtour = 0;
		dfs_tour(adj_werewolf, root_werewolf - 1);
		for (int i = 0; i < q; i++){
			tour_range_werewolf[i] = pair{tin[node_werewolf[i]], tout[node_werewolf[i]]};
		}
		for (int u = 0; u < n; u++){
			pos_werewolf[u] = tin[u];
		}
	}

	fill(pos, pos + root_human, inf);
	for (int u = 0; u < n; u++){
		pos[pos_human[u]] = pos_werewolf[u];
	}
	seg.build(1, 0, root_human - 1, pos);
	for (int i = 0; i < q; i++){
		if (seg.query(1, 0, root_human - 1, tour_range_human[i].first, tour_range_human[i].second - 1, tour_range_werewolf[i].first) < tour_range_werewolf[i].second){
			ans[i] = 1;
		}
		else{
			ans[i] = 0;
		}
	}
	return vector <int>(ans, ans + q);
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51