Submission #118846

#	Time	Username	Problem	Language	Result	Execution time	Memory
118846		Mamnoon_Siam	Werewolf (IOI18_werewolf)	C++17	100 / 100	626 ms	95228 KiB

werewolf

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

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using VI = vector<int>;
const int maxn = 4e5 + 5;

int N, M, Q;
int U[maxn], V[maxn];
namespace pre {
	int parent[maxn];
	vector<int> g[maxn], w[maxn];
	int sz[maxn], par[maxn], pw[maxn];
	int in[maxn], tour[maxn];
	int tym = 0;
	void init() {
		for(int i = 0; i < N; i++) {
			sz[i] = 1, par[i] = i;
		}
	}
	int find(int u) {
		return par[u] == u ? u : find(par[u]);
	}
	void join(int u, int v) {
		int weight = max(u, v);
		u = find(u), v = find(v);
		if(u == v) return;
		if(sz[u] > sz[v]) swap(u, v);
		par[u] = v, pw[u] = weight;
		sz[v] += sz[u];
		g[v].emplace_back(u);
		w[v].emplace_back(weight);
	}
	void dfs(int u) {
		tour[tym] = u;
		in[u] = tym++;
		for(int v : g[u]) {
			dfs(v);
		}
	}
	pair<int, int> range(int u, int weight) {
		while(par[u] != u and pw[u] <= weight)
			u = par[u];
		if(sz[u] == 1) // leaf
			return {in[u], in[u]};
		int it = upper_bound(all(w[u]), weight) - w[u].begin();
		if(it == 0) // can't go nowhere
			return {in[u], in[u]};
		int v = g[u][it - 1];
		return {in[u], in[v] + sz[v] - 1};
	}
}
namespace suf {
	int parent[maxn];
	vector<int> g[maxn], w[maxn];
	int sz[maxn], par[maxn], pw[maxn];
	int in[maxn], tour[maxn];
	int tym = 0;
	void init() {
		for(int i = 0; i < N; i++) {
			sz[i] = 1, par[i] = i;
		}
	}
	int find(int u) {
		return par[u] == u ? u : find(par[u]);
	}
	void join(int u, int v) {
		int weight = min(u, v);
		u = find(u), v = find(v);
		if(u == v) return;
		if(sz[u] > sz[v]) swap(u, v);
		par[u] = v, pw[u] = weight;
		sz[v] += sz[u];
		g[v].emplace_back(u);
		w[v].emplace_back(weight);
	}
	void dfs(int u) {
		tour[tym] = u;
		in[u] = tym++;
		for(int v : g[u]) {
			dfs(v);
		}
	}
	pair<int, int> range(int u, int weight) {
		while(par[u] != u and pw[u] >= weight)
			u = par[u];
		if(sz[u] == 1) // leaf
			return {in[u], in[u]};
		int it = upper_bound(all(w[u]), weight, [](int x, int y){ return x > y; }) - w[u].begin();
		if(it == 0) // can't go nowhere
			return {in[u], in[u]};
		int v = g[u][it - 1];
		return {in[u], in[v] + sz[v] - 1};
	}
}

vector<int> check_validity(int _N, VI X, VI Y, VI S, VI E, VI L, VI R) {
	N = _N, M = X.size(), Q = S.size();
	for(int i = 0; i < M; i++) {
		U[i] = X[i], V[i] = Y[i];
		if(U[i] > V[i]) swap(U[i], V[i]);
	}

	pre::init();
	suf::init();

	vector<int> p(M), q(M);
	iota(p.begin(), p.end(), 0);
	iota(q.begin(), q.end(), 0);
	sort(p.begin(), p.end(), [](int x, int y){ return V[x] < V[y]; });
	sort(q.begin(), q.end(), [](int x, int y){ return U[x] > U[y]; });

	for(int i : p)
		pre::join(U[i], V[i]);
	for(int i : q)
		suf::join(U[i], V[i]);

	pre::dfs(pre::find(0));
	suf::dfs(suf::find(0));

	int tour[maxn], index[maxn];
	for(int i = 0; i < N; i++) {
		index[pre::tour[i]] = i;
	}
	for(int i = 0; i < N; i++) {
		tour[i] = index[suf::tour[i]];
	}

	vector<int> ans(Q);
	struct data {
		int L, id, op, l, r;
		data() {}
		data(int _L, int _id, int _op, int _l, int _r) {
			L = _L, id = _id, op = _op, l = _l, r = _r;
		}
		bool operator < (const data &that) const {
			return L < that.L;
		}
	};

	vector<data> shit_load;

	for(int i = 0; i < Q; i++) {
		int l1, l2, r1, r2;
		tie(l1, r1) = pre::range(E[i], R[i]);
		tie(l2, r2) = suf::range(S[i], L[i]);
		shit_load.push_back(data(r2, i, +1, l1, r1));
		if(l2 != 0) shit_load.push_back(data(l2 - 1, i, -1, l1, r1));
	}

	int ft[maxn];
	memset(ft, 0, sizeof ft);
	auto update = [&](int i) {
		i++;
		for(; i < maxn; i += i & -i) ft[i]++;
	};
	auto query = [&](int l, int r) {
		r++;
		int ret = 0;
		for(; l > 0; l -= l & -l) ret -= ft[l];
		for(; r > 0; r -= r & -r) ret += ft[r];
		return ret;
	};

	sort(all(shit_load));

	int it = 0;
	for(data e : shit_load) {
		while(it < N and it <= e.L) {
			update(tour[it]);
			it++;
		}
		ans[e.id] += e.op * query(e.l, e.r);
	}
	for(int &i : ans) i = bool(i);
	return ans;
}

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