제출 #1191495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191495		vidux	Werewolf (IOI18_werewolf)	C++17	0 / 100	4088 ms	23932 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	int Q = L.size();
	int M = X.size();
	vi ans(N);
	vvi adj(N);
	for (int i = 0; i < M; i++) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	for (int t = 0; t < Q; t++) {
		int l = L[t], r = R[t];
		int s = S[t], e = E[t];
		vvi seen(2, vi(N));
		queue<pii> q;
		q.push({s, 0});
		while (q.size()) {
			auto [u, wolf] = q.front(); q.pop();
			if (seen[wolf][u]) continue;
			seen[wolf][u] = 1;
			if (u >= l && u <= r && !wolf) q.push({u, 1});
			for (int v : adj[u]) {
				if (v >= l && !wolf && !seen[0][v]) q.push({v, 0});
				if (v <= r && wolf && !seen[1][v]) q.push({v, 1});
			}
			if (seen[1][e]) break;
		}
		ans[t] = seen[1][e];
	}
	
	return ans;
}

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