Submission #392939

#	Time	Username	Problem	Language	Result	Execution time	Memory
392939		JimmyZJX	Werewolf (IOI18_werewolf)	C++14	49 / 100	4014 ms	51152 KiB

werewolf

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;

#define forR(i, n) for (int i = 0; i < (n); i++)

int n, m, q;

Vii nbs;

bool T3 = false;
Vi qt3, t3PosOf;

struct Range {
	int l, r;

	bool contains(int t) {
		return l <= t && t <= r;
	}

	static bool overlaps(Range r1, Range r2) {
		return r1.contains(r2.l) || r2.contains(r1.l);
	}
};

struct SegNode {
	int l, r;
	SegNode* left, * right;
	int minV, maxV;

	Range RangeGe(int t, int L) { // >= L
		if (t < l || t > r) return Range{ -1, -2 };

		if (minV >= L) return Range{ l, r };
		if (l == r) return Range{ -1, -2 };

		if (left->contains(t)) {
			auto range = left->RangeGe(t, L);
			if (range.r == left->r) {
				auto rR = right->RangeGe(right->l, L);
				if (rR.l == right->l) range.r = rR.r;
			}
			return range;
		} else {
			assert(right->contains(t));
			auto range = right->RangeGe(t, L);
			if (range.l == right->l) {
				auto rL = left->RangeGe(left->r, L);
				if (rL.r == left->r) range.l = rL.l;
			}
			return range;
		}
	}

	Range RangeLe(int t, int R) { // <= R
		if (t < l || t > r) return Range{ -1, -2 };

		if (maxV <= R) return Range{ l, r };
		if (l == r) return Range{ -1, -2 };

		if (left->contains(t)) {
			auto range = left->RangeLe(t, R);
			if (range.r == left->r) {
				auto rR = right->RangeLe(right->l, R);
				if (rR.l == right->l) range.r = rR.r;
			}
			return range;
		} else {
			assert(right->contains(t));
			auto range = right->RangeLe(t, R);
			if (range.l == right->l) {
				auto rL = left->RangeLe(left->r, R);
				if (rL.r == left->r) range.l = rL.l;
			}
			return range;
		}
	}

	inline bool contains(int t) {
		return l <= t && t <= r;
	}

	SegNode(int l, int r) {
		this->l = l; this->r = r;
		if (l == r) {
			left = right = nullptr;
			minV = maxV = qt3[l];
		} else {
			int mid = (l + r) / 2;
			left = new SegNode(l, mid);
			right = new SegNode(mid + 1, r);
			minV = min(left->minV, right->minV);
			maxV = max(left->maxV, right->maxV);
		}
	}

}*root;

void initT3() {
	int head;
	forR(i, n) if (nbs[i].size() == 1) {
		head = i;
		break;
	}

	Vb inT3(n); t3PosOf = Vi(n);
	inT3[head] = true; qt3.push_back(head);

	int next = -1;
	for (int x = head; x >= 0; x = next) {
		next = -1;
		for (int nb : nbs[x]) {
			if (!inT3[nb]) {
				inT3[nb] = true;
				t3PosOf[nb] = qt3.size();
				qt3.push_back(nb);
				next = nb;
			}
		}
	}
	root = new SegNode(0, n - 1);
}

int calcT3(int s, int e, int l, int r) { // [l, inf) --> [0, r]
	int ps = t3PosOf[s], pe = t3PosOf[e];

	auto rangeS = root->RangeGe(ps, l);
	auto rangeE = root->RangeLe(pe, r);

	if (Range::overlaps(rangeS,rangeE)) {
		return 1;
	}
	return 0;
}

int calc(int s, int e, int l, int r) { // [l, inf) --> [0, r]

	if (s < l || e > r || l > r) return 0;

	if (T3) return calcT3(s, e, l, r);


	Vb inS(n), inE(n);

	// pathfind 1: from s, >= l
	queue<int> q; q.push(s); inS[s] = true;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int nb : nbs[x]) {
			if (inS[nb] == false && nb >= l) {
				inS[nb] = true;
				q.push(nb);
			}
		}
	}

	// pathfind 2: from e, <= r
	q = queue<int>(); q.push(e); inE[e] = true;
	if (inS[e]) return 1;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int nb : nbs[x]) {
			if (inE[nb] == false && nb <= r) {
				inE[nb] = true;
				q.push(nb);
				if (inS[nb]) {
					// transform at nb, succeed
					return 1;
				}
			}
		}
	}

	return 0;
}

Vi check_validity(int N, Vi X, Vi Y, Vi S, Vi E, Vi	L, Vi R) {
	n = N; m = X.size(); q = S.size();

	nbs = Vii(n);
	forR(i, m) {
		nbs[X[i]].push_back(Y[i]);
		nbs[Y[i]].push_back(X[i]);
	}

	int nbs_cnt_max = 0;
	forR(i, n) nbs_cnt_max = max(nbs_cnt_max, (int)nbs[i].size());
	if (nbs_cnt_max == 2 && m == n - 1) {
		T3 = true;

		initT3();
	}

	Vi result;
	forR(i, q) {
		result.push_back(calc(S[i], E[i], L[i], R[i]));
	}

	return result;
}

#ifdef TEST_LOCAL_
int main() {
	auto result = check_validity(6, Vi{ 5, 1, 1, 3, 3, 5 }, Vi{ 1, 2, 3, 4, 0, 2 }, Vi{ 4, 4, 5 }, Vi{ 2, 2, 4 }, Vi{ 1, 2, 3 }, Vi{ 2, 2, 4 });

	return 0;
}
#endif

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