Submission #392913

#	Time	Username	Problem	Language	Result	Execution time	Memory
392913		JimmyZJX	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4073 ms	21536 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;

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

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

	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]);
	}

	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: 0 / 34
• Subtask 4: 0 / 51