제출 #299561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299561		square1001	Werewolf (IOI18_werewolf)	C++14	15 / 100	4018 ms	30020 KiB

werewolf

#include "werewolf.h"
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
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]);
	}
	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 ans;
}

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