Submission #99211

#	Time	Username	Problem	Language	Result	Execution time	Memory
99211		eriksuenderhauf	Werewolf (IOI18_werewolf)	C++11	100 / 100	3907 ms	135608 KiB

werewolf

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "werewolf.h"
#define vi vector<int>
#define pb push_back
using namespace std;
const int MAXN = 2e5 + 50;
vi adj[MAXN], ltree[MAXN], rtree[MAXN], lArr[MAXN], rArr[MAXN];
int par[MAXN], sz[MAXN], lA[MAXN], rA[MAXN], ind[MAXN];
int stL[MAXN], enL[MAXN], stR[MAXN], enR[MAXN];
int lPar[18][MAXN], rPar[18][MAXN];
set<int> comp[MAXN];
int n, m, q, t, BIT[MAXN], tmp[2*MAXN];

void add(int ind, int v) {
	ind++;
	while (ind < MAXN) {
		BIT[ind] += v;
		ind += ind & -ind;
	}
}

int sum(int ind) {
	ind++;
	int ret = 0;
	while (ind > 0) {
		ret += BIT[ind];
		ind -= ind & -ind;
	}
	return ret;
}

void ldfs(int u, int p) {
	stL[u] = t;
	lA[t++] = u;
	for (int v: ltree[u])
		if (v != p) {
			ldfs(v, u);
			lPar[0][v] = u;
		}
	enL[u] = t - 1;
}

void rdfs(int u, int p) {
	stR[u] = t;
	rA[t++] = u;
	for (int v: rtree[u])
		if (v != p) {
			rdfs(v, u);
			rPar[0][v] = u;
		}
	enR[u] = t - 1;
}

int qry(int x) {
	return x == par[x] ? x : par[x] = qry(par[x]);
}

void join(int x, int y) {
	x = qry(x), y = qry(y);
	if (x == y) return;
	if (sz[x] > sz[y]) swap(x, y);
	par[x] = y;
	sz[y] += sz[x];
	comp[y].insert(comp[x].begin(), comp[x].end());
	comp[x].clear();
}

void init() {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		sz[i] = 1;
		comp[i] = {i};
	}
}

vi check_validity(int N, vi x, vi y, vi s, vi e, vi l, vi r) {
	n = N, m = x.size(), q = l.size();
	for (int i = 0; i < m; i++) {
		adj[x[i]].pb(y[i]);
		adj[y[i]].pb(x[i]);
	}
	init();
	for (int i = 0; i < n; i++) { // r
		for (int v: adj[i]) {
			if (v > i || qry(i) == qry(v)) continue;
			int u = *(--comp[qry(v)].end());
			join(i, u);
			rtree[i].pb(u);
			rtree[u].pb(i);
		}
	}
	init();
	for (int i = n - 1; i >= 0; i--) { // l
		for (int v: adj[i]) {
			if (v < i || qry(i) == qry(v)) continue;
			int u = *(comp[qry(v)].begin());
			join(i, u);
			ltree[i].pb(u);
			ltree[u].pb(i);
		}
	}
	for (int i = 0; i < 18; i++)
		fill(lPar[i], lPar[i] + MAXN, 0), fill(rPar[i], rPar[i] + MAXN, n - 1);
	t = 0;
	ldfs(0, -1);
	t = 0;
	rdfs(n - 1, -1);
	for (int i = 1; i < 18; i++)
		for (int j = 0; j < n; j++)
			lPar[i][j] = lPar[i - 1][lPar[i - 1][j]],
			rPar[i][j] = rPar[i - 1][rPar[i - 1][j]];
	for (int i = 0; i < n; i++)
		ind[rA[i]] = i;
	vi ret;
	for (int i = 0; i < q; i++) {
		ret.pb(0);
		int u = s[i];
		for (int j = 17; j >= 0; j--)
			if (lPar[j][u] >= l[i])
				u = lPar[j][u];
		lArr[stL[u]].pb(i);
		rArr[enL[u]].pb(i);
	}
	for (int i = 0; i < n; i++) {
		for (int j: lArr[i]) {
			int u = e[j];
			for (int k = 17; k >= 0; k--)
				if (rPar[k][u] <= r[j])
					u = rPar[k][u];
			tmp[j] = sum(enR[u]) - sum(stR[u] - 1);
		}
		add(ind[lA[i]], 1);
		for (int j: rArr[i]) {
			int u = e[j];
			for (int k = 17; k >= 0; k--)
				if (rPar[k][u] <= r[j])
					u = rPar[k][u];
			if (sum(enR[u]) - sum(stR[u] - 1) != tmp[j])
				ret[j] = 1;
			else
				ret[j] = 0;
		}
	}
	return ret;
}

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