Submission #601845

#	Time	Username	Problem	Language	Result	Execution time	Memory
601845		DanShaders	Werewolf (IOI18_werewolf)	C++17	100 / 100	2522 ms	406820 KiB

werewolf

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

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 2e5 + 10;

const int MEMORY = 400 << 20;

char memory[MEMORY];
size_t memory_ptr = 0;

void *operator new(size_t sz) {
	auto res = memory + memory_ptr;
	memory_ptr += sz;
	return res;
}

void operator delete(void *) {}
void operator delete(void *, size_t) {}

struct Query {
	int s, e, l, r, i;
};

int color[N];
vector<int> g[N];

struct DSU {
	int parent[N];
	vector<int> comp[N];

	DSU() {
		iota(all(parent), 0);
		for (int i = 0; i < N; ++i) {
			comp[i].push_back(i);
		}
	}

	int get(int u) {
		if (u == parent[u]) {
			return u;
		}
		return parent[u] = get(parent[u]);
	}
} dsu;

struct DSU2 {
	int parent[N], rank[N];

	DSU2() {
		iota(all(parent), 0);
	}

	int get(int u) {
		if (u == parent[u]) {
			return u;
		}
		return parent[u] = get(parent[u]);
	}

	bool merge(int a, int b) {
		a = get(a);
		b = get(b);
		if (a == b) {
			return false;
		}
		if (rank[a] == rank[b]) {
			++rank[a];
		}
		if (rank[a] < rank[b]) {
			swap(a, b);
		}
		parent[b] = a;
		return true;
	}
} dsu2;

bool check_reachable(int u, int barrier, int c, int p = -1) {
	if (u < barrier) {
		return false;
	}
	if (color[u] == c) {
		return true;
	}
	for (int v : g[u]) {
		if (v != p && check_reachable(v, barrier, c, u)) {
			return true;
		}
	}
	return false;
}

char used[N];
int sz[N];

int dfs_sz(int u, int p = -1) {
	sz[u] = 1;
	for (int v : g[u]) {
		if (v != p && !used[v]) {
			sz[u] += dfs_sz(v, u);
		}
	}
	return sz[u];
}

int find_centroid(int u, int csz, int p = -1) {
	for (int v : g[u]) {
		if (v != p && !used[v] && 2 * sz[v] > csz) {
			return find_centroid(v, csz, u);
		}
	}
	return u;
}

const int LOG = 20;

int gmn[LOG][N];

struct Node {
	int depth;
	int parent;
	vector<int> children;
	int version;
	unordered_map<int, int> where;
};

int current_version = 15;

Node node_at[N];

int centroid_dfs(int u, int parent = -1, int depth = 0) {
	u = find_centroid(u, dfs_sz(u));

	auto &node = node_at[u];
	node.depth = depth;
	node.parent = parent;

	queue<tuple<int, int, int>> bfs;
	bfs.push({u, u, -1});
	while (sz(bfs)) {
		auto [v, mn, p] = bfs.front();
		gmn[depth][v] = node.where[v] = mn;
		bfs.pop();
		for (int w : g[v]) {
			if (p != w && !used[w]) {
				bfs.push({w, min(mn, w), v});
			}
		}
	}

	used[u] = 1;
	for (int v : g[u]) {
		if (!used[v]) {
			node.children.push_back(centroid_dfs(v, u, depth + 1));
		}
	}
	return u;
}

vector<int> check_validity(int, vector<int> us, vector<int> vs, vector<int> qs, vector<int> qe, vector<int> ql, vector<int> qr) {
	vector<Query> queries;
	for (int i = 0; i < sz(qs); ++i) {
		queries.push_back({qe[i], qs[i], qr[i], ql[i], i});
	}
	vector<pair<int, int>> e1, e2;
	for (int i = 0; i < sz(us); ++i) {
		e1.emplace_back(us[i], vs[i]);
	}
	e2 = e1;
	iota(all(color), 0);
	sort(all(e1), [](const auto &x, const auto &y) {
		return max(x.x, x.y) < max(y.x, y.y);
	});
	sort(all(e2), [](const auto &x, const auto &y) {
		return min(x.x, x.y) > min(y.x, y.y);
	});
	for (auto [u, v] : e2) {
		if (dsu2.merge(u, v)) {
			g[u].push_back(v);
			g[v].push_back(u);
		}
	}
	sort(all(queries), [](const auto &x, const auto &y) {
		return x.l < y.l;
	});
	vector<int> ans(sz(queries));

	centroid_dfs(0);

	int e1i = 0;
	for (auto [s, e, l, r, i] : queries) {
		while (e1i < sz(e1) && max(e1[e1i].x, e1[e1i].y) <= l) {
			int a = dsu.get(e1[e1i].x), b = dsu.get(e1[e1i].y);
			++e1i;
			if (a == b) {
				continue;
			}
			if (sz(dsu.comp[a]) < sz(dsu.comp[b])) {
				swap(a, b);
			}

			++current_version;
			for (int u : dsu.comp[b]) {
				auto curr = u;
				while (curr != -1 && node_at[curr].version != current_version) {
					node_at[curr].version = current_version;

					auto it = node_at[curr].where.find(a);
					if (it == node_at[curr].where.end()) {
						node_at[curr].where[a] = node_at[curr].where[b];
					} else {
						it->second = max(it->second, node_at[curr].where[b]);
					}
					curr = node_at[curr].parent;
				}
				color[u] = a;
			}
			dsu.comp[a].insert(end(dsu.comp[a]), all(dsu.comp[b]));
			vector<int>().swap(dsu.comp[b]);

			dsu.parent[b] = a;
		}
		auto curr = e;
		while (curr != -1) {
			if (gmn[node_at[curr].depth][e] >= r) {
				auto it = node_at[curr].where.find(color[s]);
				if (it != node_at[curr].where.end() && it->second >= r) {
					ans[i] = 1;
					break;
				}
			}
			curr = node_at[curr].parent;
		}
		// ans[i] = check_reachable(e, r, color[s]);
	}
	return ans;
}

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