Submission #299568

#	Time	Username	Problem	Language	Result	Execution time	Memory
299568		square1001	Werewolf (IOI18_werewolf)	C++14	34 / 100	1909 ms	51060 KiB

werewolf

#include "werewolf.h"
#include <queue>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class sparse_table {
private:
	int N, bits; bool ismax;
	vector<int> level;
	vector<vector<int> > val;
public:
	sparse_table() : N(0), bits(0), val() {};
	sparse_table(const vector<int>& arr, const string& type_) : N(arr.size()), ismax(type_ == "max") {
		bits = 1;
		while((1 << bits) < N) {
			++bits;
		}
		level = vector<int>(N + 1, 0);
		for(int i = 1; i <= N; ++i) {
			while((2 << level[i]) < i) {
				++level[i];
			}
		}
		val = vector<vector<int> >(bits);
		val[0] = arr;
		for(int i = 1; i < bits; ++i) {
			val[i].resize(N - (1 << i) + 1);
			for(int j = 0; j <= N - (1 << i); ++j) {
				val[i][j] = (ismax ? max(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]) : min(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]));
			}
		}
	}
	int range_query(int l, int r) const {
		return (ismax ? max(val[level[r - l]][l], val[level[r - l]][r - (1 << level[r - l])]) : min(val[level[r - l]][l], val[level[r - l]][r - (1 << level[r - l])]));
	}
};
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) {
	int M = X.size(), Q = S.size();
	vector<vector<int> > G(N);
	for(int i = 0; i < M; ++i) {
		G[X[i]].push_back(Y[i]);
		G[Y[i]].push_back(X[i]);
	}
	int deg1 = 0, deg2 = 0;
	for(int i = 0; i < N; ++i) {
		if(G[i].size() == 1) ++deg1;
		if(G[i].size() == 2) ++deg2;
	}
	bool subtask3 = (N >= 3 && deg1 == 2 && deg2 == N - 2);
	if(subtask3) {
		int ini = -1;
		for(int i = 0; i < N; ++i) {
			if(G[i].size() == 1) {
				ini = i;
				break;
			}
		}
		int pre = -1;
		vector<int> seq = { ini };
		for(int i = 1; i < N; ++i) {
			for(int j : G[seq.back()]) {
				if(j != pre) {
					pre = seq.back();
					seq.push_back(j);
					break;
				}
			}
		}
		vector<int> iseq(N);
		for(int i = 0; i < N; ++i) {
			iseq[seq[i]] = i;
		}
		sparse_table smin(seq, "min"), smax(seq, "max");
		vector<int> ans(Q);
		for(int i = 0; i < Q; ++i) {
			int la = -1, ra = iseq[S[i]] + 1;
			while(ra - la > 1) {
				int ma = (la + ra) / 2;
				int g = smin.range_query(ma, iseq[S[i]] + 1);
				if(g >= L[i]) ra = ma;
				else la = ma;
			}
			// LEFT-S = RA
			int lb = iseq[S[i]], rb = N + 1;
			while(rb - lb > 1) {
				int mb = (lb + rb) / 2;
				int g = smin.range_query(iseq[S[i]], mb);
				if(g >= L[i]) lb = mb;
				else rb = mb;
			}
			// RIGHT-S = LB
			int lc = -1, rc = iseq[E[i]] + 1;
			while(rc - lc > 1) {
				int mc = (lc + rc) / 2;
				int g = smax.range_query(mc, iseq[E[i]] + 1);
				if(g <= R[i]) rc = mc;
				else lc = mc;
			}
			// LEFT-E = RC
			int ld = iseq[E[i]], rd = N + 1;
			while(rd - ld > 1) {
				int md = (ld + rd) / 2;
				int g = smax.range_query(iseq[E[i]], md);
				if(g <= R[i]) ld = md;
				else rd = md;
			}
			// RIGHT-E = LD
			if(max(ra, rc) < min(lb, ld)) {
				ans[i] = 1;
			}
		}
		return ans;
	}
	else {
		vector<int> ans(Q);
		for(int i = 0; i < Q; ++i) {
			vector<bool> visa(N), visb(N);
			queue<int> qa, qb;
			qa.push(S[i]); visa[S[i]] = true;
			qb.push(E[i]); visb[E[i]] = true;
			while(!qa.empty()) {
				int u = qa.front(); qa.pop();
				for(int j : G[u]) {
					if(j >= L[i] && !visa[j]) {
						visa[j] = true;
						qa.push(j);
					}
				}
			}
			while(!qb.empty()) {
				int u = qb.front(); qb.pop();
				for(int j : G[u]) {
					if(j <= R[i] && !visb[j]) {
						visb[j] = true;
						qb.push(j);
					}
				}
			}
			for(int j = 0; j < N; ++j) {
				if(visa[j] && visb[j]) {
					ans[i] = 1;
				}
			}
		}
	}
	return vector<int>();
}

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