Submission #388408

#	Time	Username	Problem	Language	Result	Execution time	Memory
388408		morato	Werewolf (IOI18_werewolf)	C++17	100 / 100	1280 ms	212888 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int MAXL = 20;
const int INF = 1e9;
const int MAXN = 4e5 + 5;

class FenwickTree
{
	public:

		FenwickTree(int _n = MAXN - 1) {
			n = _n;
			for (int i = 0; i <= n; i++) {
				bit[i] = 0;
			}
		}

		void update(int x, int val) {
			for (; x <= n; x += x & -x)
				bit[x] += val;
		}

		int query(int x) {
			int ans = 0;
			for (; x > 0; x -= x & -x) 
				ans += bit[x];
			return ans;
		}

	private:

		int n;

		int bit[MAXN];

} bit;

class KRT
{
	public:

		KRT(int _n = 0): n(_n) {
			curTimer = 0;
			for (int i = 1; i <= n; i++) {
				p[i] = i;
			}
		}

		void init(int _n) {
			n = _n;
			for (int i = 1; i <= n; i++) {
				p[i] = i;
			}
		}

		int getTin(int v) { return tin[v]; }
		int getTout(int v) { return tout[v]; }
		int getRoot(int v) { return p[v] == v ? v : p[v] = getRoot(p[v]); }

		void addEdge(int v, int u, int w, int flag) {
			v = getRoot(v);
			u = getRoot(u);
			if (u == v) return;
			++n;
			p[n] = p[u] = p[v] = n;
			adj[n].push_back(v);
			adj[n].push_back(u);
			anc[v][0] = anc[u][0] = {n, w};
            anc[n][0] = make_pair(n, (flag ? 0 : INF));
		}

		void dfs(int cur) {
			tin[cur] = ++curTimer;
			for (int viz : adj[cur]) {
				dfs(viz);
			}
			tout[cur] = curTimer;
		}

		int get(int a, int b, int flag) {
			return flag ? max(a, b) : min(a, b);
		}

		void buildKRT(int flag) {
			for (int d = 1; d < MAXL; d++) {
				for (int i = 1; i <= n; i++) {
					auto mid = anc[i][d - 1];
					auto target = anc[mid.first][d - 1];
					anc[i][d] = {target.first, get(mid.second, target.second, flag)};
				}
			}
			dfs(n);
		}

		bool compare(int limit, int value, int flag) {
			return flag ? limit >= value : limit <= value;
		}

		int goUp(int v, int limit, int flag) {
			for (int j = MAXL - 1; j >= 0; j--) {
				if (compare(limit, anc[v][j].second, flag)) {
					v = anc[v][j].first;
				}
			}
			return v;
		}

	private:

		int n;
		int curLen;
		int curTimer;

		int p[MAXN];
		int tin[MAXN];
		int tout[MAXN];

		vector<int> adj[MAXN];

		pair<int, int> anc[MAXN][MAXL];

} krtMin, krtMax;

struct Event
{
	int tipo, idx;
	int x, y;

	Event() {}

	Event(int _t, int _i, int _x, int _y): tipo(_t), idx(_i), x(_x), y(_y) {}

	bool operator <(const Event &e) const {
		if (x == e.x) return tipo < e.tipo;
		return x < e.x;
	}
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int n = N;
	krtMin.init(n);
	krtMax.init(n);
	vector<pair<int, pair<int, int>>> edges[2];
	int m = (int) X.size();
	for (int i = 0; i < m; i++) {
		X[i]++, Y[i]++;
		edges[0].push_back(make_pair(min(X[i], Y[i]), make_pair(X[i], Y[i])));
		edges[1].push_back(make_pair(max(X[i], Y[i]), make_pair(X[i], Y[i])));
	}
	for (int i : {0, 1}) {
		sort(edges[i].begin(), edges[i].end());
	}
    reverse(edges[0].begin(), edges[0].end());
	for (int i = 0; i < m; i++) {
		int w = edges[0][i].first;
		int v = edges[0][i].second.first;
		int u = edges[0][i].second.second;
		krtMin.addEdge(v, u, w, 0);
	}
	for (int i = 0; i < m; i++) {
		int w = edges[1][i].first;
		int v = edges[1][i].second.first;
		int u = edges[1][i].second.second;
		krtMax.addEdge(v, u, w, 1);
	}
	krtMin.buildKRT(0);
	krtMax.buildKRT(1);
	int q = (int) S.size();
	vector<Event> sweep;
	for (int i = 1; i <= n; i++) {
		int x = krtMax.getTin(i);
		int y = krtMin.getTin(i);
		sweep.emplace_back(0, -1, x, y);
	}
	vector<int> ans(q);
	for (int i = 0; i < q; i++) {
		S[i]++, E[i]++, L[i]++, R[i]++;
		int maxHuman = krtMin.goUp(S[i], L[i], 0);
		int maxWerewolf = krtMax.goUp(E[i], R[i], 1);
		int y1 = krtMin.getTin(maxHuman);
		int y2 = krtMin.getTout(maxHuman);
		int x1 = krtMax.getTin(maxWerewolf);
		int x2 = krtMax.getTout(maxWerewolf);
		sweep.emplace_back(1, i, x1 - 1, y2);
		sweep.emplace_back(1, i, x2, y1 - 1);
		sweep.emplace_back(2, i, x1 - 1, y1 - 1);
		sweep.emplace_back(2, i, x2, y2);
	}
	sort(sweep.begin(), sweep.end());
	for (auto event : sweep) {
		if (event.tipo == 0) {
			bit.update(event.y, 1);
		} else if (event.tipo == 1) {
			ans[event.idx] -= bit.query(event.y);
		} else {
			ans[event.idx] += bit.query(event.y);
		}
	}
	for (int& x : ans) {
		x = !!x;
	}
	return ans;
}

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