Submission #456476

#	Time	Username	Problem	Language	Result	Execution time	Memory
456476		flappybird	Werewolf (IOI18_werewolf)	C++14	0 / 100	1002 ms	148080 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define MAX 401010
#define MAXS 18
#define INF 1010101010
ll N, M;
vector<ll> X, Y, S, E, L, R;
ll prt1[MAX], prt2[MAX]; //tree
ll val1[MAX], val2[MAX]; //tree
ll ord1[MAX], ord2[MAX]; //tree
ll l1[MAX], l2[MAX]; //tree
ll r1[MAX], r2[MAX]; //tree
ll sp1[MAX][MAXS], sp2[MAX][MAXS];
pair<ll, ll> range1[MAX], range2[MAX];
vector<ll> adj[MAX];
struct dsu {
	vector<ll> p;
	dsu() {}
	dsu(ll n) {
		N = n;
		p.clear();
		p.resize(N);
		ll i;
		for (i = 0; i < N; i++) p[i] = i;
	}
	ll find(ll x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	}
	void uni(ll u, ll v) {
		u = find(u);
		v = find(v);
		if (u == v) return;
		p.push_back(p.size());
		p[v] = p[u] = p.size() - 1;
	}
};
//merge_sort_segtree %$%#%#%$
struct segtree {
	ll N, s;
	vector<vector<ll>> tree;
	vector<ll> l, r;
	ll get(vector<ll>& v, ll l, ll r) {
		return upper_bound(v.begin(), v.end(), r) - upper_bound(v.begin(), v.end(), l);
	}
	void init(ll x = 1) {
		if (x >= s) {
			if (!tree[x].empty()) sort(tree[x].begin(), tree[x].end());
			l[x] = r[x] = x - s;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		tree[x] = tree[x * 2];
		for (auto v : tree[x * 2 + 1]) tree[x].push_back(v);
		sort(tree[x].begin(), tree[x].end());
	}
	segtree() {}
	segtree(ll _N) {
		N = _N;
		s = 1 << (ll)ceil(log2(N));
		tree.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
	}
	ll query(ll low, ll high, ll s, ll e, ll loc = 1) {
		if (low == l[loc] && high == r[loc]) return get(tree[loc], s, e);
		if (high <= r[loc * 2]) return query(low, high, s, e, loc * 2);
		if (low >= l[loc * 2 + 1]) return query(low, high, s, e, loc * 2 + 1);
		return query(low, r[loc * 2], s, e, loc * 2) | query(l[loc * 2 + 1], high, s, e, loc * 2 + 1);
	}
};
void make_tree(ll mode = 0) {
	ll i;
	dsu d = dsu(N);
	if (!mode) {
		for (i = 0; i < 2 * N - 1; i++) l1[i] = r1[i] = -1;
		for (i = 0; i < N; i++) {
			for (auto v : adj[i]) {
				if (v > i) continue;
				if (d.find(v) == d.find(i)) continue;
				ll ii, vv;
				ii = d.find(i);
				vv = d.find(v);
				d.uni(ii, vv);
				val1[d.p.size() - 1] = i;
				l1[d.p.size() - 1] = ii;
				r1[d.p.size() - 1] = vv;
				prt1[ii] = prt1[vv] = d.p.size() - 1;
			}
		}
	}
	else {
		for (i = 0; i < 2 * N - 1; i++) l2[i] = r2[i] = -1;
		for (i = N - 1; i >= 0; i--) {
			for (auto v : adj[i]) {
				if (i > v) continue;
				if (d.find(v) == d.find(i)) continue;
				ll ii, vv;
				ii = d.find(i);
				vv = d.find(v);
				d.uni(i, v);
				val2[d.p.size() - 1] = i;
				l2[d.p.size() - 1] = ii;
				r2[d.p.size() - 1] = vv;
				prt2[ii] = prt2[vv] = d.p.size() - 1;
			}
		}
	}
}
ll cnt;
//rev_ord
void dfs1(ll x) {
	if (x < N) {
		ord1[x] = cnt++;
		range1[x] = { ord1[x], ord1[x] };
		return;
	}
	dfs1(l1[x]);
	dfs1(r1[x]);
	range1[x] = { range1[l1[x]].first, range1[r1[x]].second };
}
void dfs2(ll x) {
	if (x < N) {
		ord2[x] = cnt++;
		range2[x] = { ord2[x], ord2[x] };
		return;
	}
	dfs2(l2[x]);
	dfs2(r2[x]);
	range2[x] = { range2[l2[x]].first, range2[r2[x]].second };
}
std::vector<int> check_validity(int _N, vector<int> _X, vector<int> _Y, vector<int> _S, vector<int> _E, vector<int> _L, vector<int> _R) {
	tie(N, X, Y, S, E, L, R) = make_tuple(_N, _X, _Y, _S, _E, _L, _R);
	vector<ll> ret;
	ll i;
	M = X.size();
	for (i = 0; i < M; i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
	make_tree(0);
	make_tree(1);
	prt1[2 * N - 2] = prt2[2 * N - 2] = 2 * N - 2;
	dfs1(2 * N - 2);
	cnt = 0;
	dfs2(2 * N - 2);
	ll Q = S.size();
	segtree mseg;
	mseg = segtree(N);
	for (i = 0; i <= 2 * N - 2; i++) sp1[i][0] = prt1[i];
	for (i = 0; i <= 2 * N - 2; i++) sp2[i][0] = prt2[i];
	for (ll k = 1; k < MAXS; k++) {
		for (i = 0; i <= 2 * N - 2; i++) {
			sp1[i][k] = sp1[sp1[i][k - 1]][k - 1];
			sp2[i][k] = sp2[sp2[i][k - 1]][k - 1];
		}
	}
	for (i = 0; i < N; i++) mseg.tree[mseg.s + ord1[i]].push_back(ord2[i]);
	mseg.init();
	for (i = 0; i < Q; i++) {
		ll s, e, l, r;
		s = S[i];
		e = E[i];
		l = L[i];
		r = R[i];
		ll v = e;
		for (ll k = MAXS - 1; k >= 0; k--) if (val1[sp1[v][k]] <= r) v = sp1[v][k];
		pair<ll, ll> wolf = range1[v];
		v = s;
		for (ll k = MAXS - 1; k >= 0; k--) if (val2[sp2[v][k]] >= l) v = sp2[v][k];
		pair<ll, ll> human = range2[v];
		if (mseg.query(wolf.first, wolf.second, human.first, human.second)) ret.push_back(1);
		else ret.push_back(0);
	}
	return ret;
}

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