Submission #820562

#	Time	Username	Problem	Language	Result	Execution time	Memory
820562		pavement	Werewolf (IOI18_werewolf)	C++17	100 / 100	1403 ms	287928 KiB

werewolf

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

#define pb push_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define mt make_tuple

using iii = tuple<int, int, int>;

int hpos, wpos, to[200005], link[200005], sz[200005], rep[200005], ancH[600005][25], ancW[600005][25], depH[600005], depW[600005], stH[600005], edH[600005], stW[600005], edW[600005];
vector<int> hadj[600005], wadj[600005];
iii human[400005], wolf[400005];

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
}

void dfsH(int n, int e = -1) {
	ancH[n][0] = e;
	for (int i = 1; i <= 20; i++)
		if (ancH[n][i - 1] != -1)
			ancH[n][i] = ancH[ancH[n][i - 1]][i - 1];
	int minst = 1e9, maxed = -1e9;
	for (auto u : hadj[n])
		if (u != e) {
			depH[u] = depH[n] + 1;
			dfsH(u, n);
			minst = min(minst, stH[u]);
			maxed = max(maxed, edH[u]);
		}
	stH[n] = minst;
	edH[n] = maxed;
	if (hadj[n].empty())
		stH[n] = edH[n] = hpos++;
}

void dfsW(int n, int e = -1) {
	ancW[n][0] = e;
	for (int i = 1; i <= 20; i++)
		if (ancW[n][i - 1] != -1)
			ancW[n][i] = ancW[ancW[n][i - 1]][i - 1];
	int minst = 1e9, maxed = -1e9;
	for (auto u : wadj[n])
		if (u != e) {
			depW[u] = depW[n] + 1;
			dfsW(u, n);
			minst = min(minst, stW[u]);
			maxed = max(maxed, edW[u]);
		}
	stW[n] = minst;
	edW[n] = maxed;
	if (wadj[n].empty())
		stW[n] = edW[n] = wpos++;
}

struct node {
	node *left, *right;
	int S, E;
	vector<int> val;
	node(int _s, int _e) : S(_s), E(_e) {
		if (S == E) {
			val.pb(to[S]);
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
		merge(left->val.begin(), left->val.end(), right->val.begin(), right->val.end(), back_inserter(val));
	}
	bool qry(int l, int r, int l2, int r2) {
		if (l > E || r < S) return 0;
		if (l <= S && E <= r) {
			auto it = lower_bound(val.begin(), val.end(), l2);
			if (it == val.end() || *it > r2) return 0;
			return 1;
		}
		return left->qry(l, r, l2, r2) || right->qry(l, r, l2, r2);
	}
} *root;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	memset(ancH, -1, sizeof ancH);
	memset(ancW, -1, sizeof ancW);
	int M = X.size();
	for (int i = 0; i < N; i++) {
		link[i] = rep[i] = i;
		sz[i] = 1;
	}
	for (int i = 0; i < M; i++) {
		human[i] = mt(min(X[i], Y[i]), X[i], Y[i]);
		wolf[i] = mt(max(X[i], Y[i]), X[i], Y[i]);
	}
	sort(human, human + X.size(), greater<iii>());
	sort(wolf, wolf + X.size());
	for (int i = 0; i < M; i++) {
		auto [w, u, v] = human[i];
		int a = rep[find(u)], b = rep[find(v)];
		if (a != b) {
			hadj[N + i].pb(a);
			hadj[N + i].pb(b);
		} else {
			hadj[N + i].pb(a);
		}
		unite(u, v);
		rep[find(u)] = N + i;
	}
	for (int i = 0; i < N; i++) {
		link[i] = rep[i] = i;
		sz[i] = 1;
	}
	for (int i = 0; i < M; i++) {
		auto [w, u, v] = wolf[i];
		int a = rep[find(u)], b = rep[find(v)];
		if (a != b) {
			wadj[N + i].pb(a);
			wadj[N + i].pb(b);
		} else {
			wadj[N + i].pb(a);
		}
		unite(u, v);
		rep[find(u)] = N + i;
	}
	dfsH(N + M - 1);
	dfsW(N + M - 1);
	for (int i = 0; i < N; i++)
		to[stH[i]] = stW[i];
	root = new node(0, N - 1);
	int Q = S.size();
	vector<int> A;
	for (int i = 0; i < Q; i++) {
		for (int j = 20; j >= 0; j--)
			if (ancH[S[i]][j] != -1 && g0(human[ancH[S[i]][j] - N]) >= L[i]) S[i] = ancH[S[i]][j];
		for (int j = 20; j >= 0; j--)
			if (ancW[E[i]][j] != -1 && g0(wolf[ancW[E[i]][j] - N]) <= R[i]) E[i] = ancW[E[i]][j];
		A.pb(root->qry(stH[S[i]], edH[S[i]], stW[E[i]], edW[E[i]]));
	}
	return A;
}

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