Submission #1134974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134974		xnqs	Werewolf (IOI18_werewolf)	C++17	7 / 100	4094 ms	47760 KiB

werewolf

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include "werewolf.h"

enum NodeColorTypes {
	White,
	Black,
};

const int BLK_SIZE = 1;

struct MoQuery {
	int src, dest;
	int l, r;
	int idx;
	MoQuery():
		src(0), dest(0), l(0), r(0), idx(0) {}
	MoQuery(int src, int dest, int l, int r, int idx):
		src(src), dest(dest), l(l), r(r), idx(idx) {}

	bool operator < (const MoQuery& other) const {
		if (this->l/BLK_SIZE!=other.l/BLK_SIZE) return this->l/BLK_SIZE < other.l/BLK_SIZE;
		return this->r < other.r;
	}
};

class DSURollback {
private:
	struct DSUState {
		int a, old_sz, b, old_t;
		DSUState():
			a(0), old_sz(0), b(0), old_t(0) {}
		DSUState(int a, int old_sz, int b, int old_t):
			a(a), old_sz(old_sz), b(b), old_t(old_t) {}
	};
	std::vector<int> t;
	std::vector<int> sz;
	std::vector<DSUState> stk;
public:
	DSURollback(int n = 0) {
		t.assign(n,0); std::iota(t.begin(),t.end(),0);
		sz.assign(n,1);
	}

	int Find(int k) {
		return ((t[k]==k) ? k : Find(t[k]));
	}

	int Unite(int a, int b) {
		int ra = Find(a);
		int rb = Find(b);

		if (ra==rb) {
			return 0;
		}

		stk.emplace_back(ra,sz[ra],rb,t[rb]);
		sz[ra] += sz[rb];
		t[rb] = ra;
		return 1;
	}

	int Undo() {
		if (stk.empty()) {
			return 0;
		}

		auto [a, old_sz, b, old_t] = stk.back();
		stk.pop_back();

		sz[a] = old_sz;
		t[b] = old_t;
		return 1;
	}
};

int gs, q;
std::vector<std::vector<int>> adj_list;
std::vector<MoQuery> queries_brute;
std::vector<MoQuery> queries_mo;
std::vector<int> ans;

// white (0..gs-1) -> black (gs..2*gs-1), black -> white
int Not(int k) {
	return ((k<gs) ? k+gs : k-gs);
}

int node_color(int k) {
	return ((k<gs) ? White : Black);
}

// handle black/white dsus separately and brute force check the virtual white->black edges between [l, r] in sqrt
void solve_brute_queries() {
	std::sort(queries_brute.begin(),queries_brute.end(),[](const MoQuery& a, const MoQuery& b) {
		return a.l > b.l;
	});

	DSURollback dsu_white(gs), dsu_black(gs);
	std::vector<int> undos_black(gs+5,0);
	std::vector<char> activated_white(gs,0);
	std::vector<char> activated_black(gs+5,0);
	int l = gs; // [l, oo]
	int r = 0; // [-oo, r)
	while (r<gs) {
		for (const auto& i : adj_list[r]) {
			// checking if i is white because white < gs
			if (node_color(i)==White&&activated_black[i]) {
				undos_black[r] += dsu_black.Unite(r,i);
			}
		}
		activated_black[r] = 1;
		++r;

#ifdef DBG
		for (int i = 0; i < gs; i++) {
			std::cout << undos_black[i] << " ";
		}
		std::cout << "\n";
#endif
	}

	for (auto [a, b, ql, qr, qidx] : queries_brute) {
		// invariant: l = r
		while (l>ql) {
			--l;
			for (const auto& i : adj_list[l]) {
				if (node_color(i)==White&&activated_white[i]) {
					dsu_white.Unite(l,i);
				}
			}
			activated_white[l] = 1;

			while (undos_black[r-1]>0) {
				--undos_black[r-1];
				dsu_black.Undo();
			}
			activated_black[r-1] = 0;
			--r;
		}

		// increase r to qr+1
		while (r<qr+1) {
			for (const auto& i : adj_list[r]) {
				// checking if i is white because white < gs
				if (node_color(i)==White&&activated_black[i]) {
					undos_black[r] += dsu_black.Unite(r,i);
				}
			}
			activated_black[r] = 1;
			++r;
		}

		// there is a virtual edge between white_i and black_i
		for (int i = l; i < r; i++) {
			if (dsu_white.Find(a)==dsu_white.Find(i)
			  &&dsu_black.Find(i)==dsu_black.Find(b)) {
				ans[qidx] = 1;
			}
		}

		// revert right pointer
		while (r>l) {
			while (undos_black[r-1]>0) {
				--undos_black[r-1];
				dsu_black.Undo();
			}
			activated_black[r-1] = 0;
			--r;
		}
	}
}

void solve_mo_queries() {
	std::sort(queries_mo.begin(),queries_mo.end());

	int curr_blk = -1;
	int l = -1, r = -1;
	DSURollback dsu(2*gs);
	std::vector<char> activated;
	for (auto [a, b, ql, qr, qidx] : queries_mo) {
		if (ql/BLK_SIZE!=curr_blk) {
			curr_blk = ql/BLK_SIZE;
			l = (curr_blk+1)*BLK_SIZE;
			r = l-1;
			activated.assign(2*gs,0);
			while (dsu.Undo());

			// activate white nodes (human nodes [l, oo])
			for (int i = l; i < gs; i++) {
				for (const auto& j : adj_list[i]) {
					if (activated[j]) {
						dsu.Unite(i,j);
					}
				}
				activated[i] = 1;
			}

			// activate black nodes (werewolf nodes [-oo, r])
			for (int i = 0; i <= r; i++) {
				for (const auto& j : adj_list[Not(i)]) {
					if (activated[j]) {
						dsu.Unite(Not(i),j);
					}
				}
				activated[Not(i)] = 1;
			}
		}

		// add werewolf nodes
		while (r<qr) {
			++r;
			for (const auto& i : adj_list[Not(r)]) {
				if (activated[i]) {
					dsu.Unite(Not(r),i);
				}
			}
			activated[Not(r)] = 1;
		}

		// add human nodes
		int undos = 0;
		while (l>ql) {
			--l;
			for (const auto& i : adj_list[l]) {
				if (activated[i]) {
					undos += dsu.Unite(l,i);
				}
			}
			activated[l] = 1;
		}

		ans[qidx] = (dsu.Find(a)==dsu.Find(Not(b)));

		// revert left pointer
		while (l<(curr_blk+1)*BLK_SIZE) {
			activated[l] = 0;
			++l;
		}
		while (undos--) {
			dsu.Undo();
		}
	}
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	gs = N;
	q = static_cast<int>(S.size());
	adj_list.assign(2*gs,std::vector<int>());
	ans.assign(q,0);
	for (int i = 0; i < static_cast<int>(X.size()); i++) {
		adj_list[X[i]].emplace_back(Y[i]);
		adj_list[Y[i]].emplace_back(X[i]);
		adj_list[Not(X[i])].emplace_back(Not(Y[i]));
		adj_list[Not(Y[i])].emplace_back(Not(X[i]));
	}

	for (int i = 0; i < gs; i++) {
		adj_list[i].emplace_back(Not(i));
		adj_list[Not(i)].emplace_back(i);
	}

	for (int i = 0; i < q; i++) {
		int a = S[i];
		int b = E[i];
		int l = L[i];
		int r = R[i];

		if (l/BLK_SIZE==r/BLK_SIZE) {
			queries_brute.emplace_back(a,b,l,r,i);
			//queries_mo.emplace_back(a,b,l,r,i);
		}
		else {
			queries_brute.emplace_back(a,b,l,r,i);
			//queries_mo.emplace_back(a,b,l,r,i);
		}
	}

	solve_brute_queries();
	solve_mo_queries();

	return ans;
}

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