제출 #604070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604070		SOOS	늑대인간 (IOI18_werewolf)	C++14	0 / 100	127 ms	28124 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3005;
const int MAX_M = 6005;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int M = X.size();
	vector<int> adj[MAX_M];
	for (int i = 0; i < M; i++) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	vector<int> result;

	int Q = S.size();
	for (int i = 0; i < Q; i++) {
		bool reachable = false;
		queue<int> qs, qe;
		bool visited_s[MAX_N] = {false}, visited_e[MAX_N] = {false};

		if (S[i] < L[i] || E[i] > R[i]) {
			result.push_back(false);
			continue;
		}

		qs.push(S[i]); visited_s[S[i]] = true;
		qe.push(E[i]); visited_e[E[i]] = true;


		while (!qs.empty()) {
			int n = qs.front(); qs.pop();
			for (auto u: adj[n]) {
				if (visited_s[u] || u < L[i]) continue;
				visited_s[u] = true;
				qs.push(u);
			}
		}
		
		/*for (int j = 0; j < N; j++) {
			cout << visited_s[j];
		}
		cout << endl;*/

		while (!qe.empty()) {
			int n = qe.front(); qe.pop();
			for (auto u: adj[n]) {
				if (visited_e[u] || u > R[i]) continue;
				visited_e[u] = true;
				if (visited_s[u]) {
					reachable = true;
					// break;
				}
				qe.push(u);
			}
		}

		/*for (int j = 0; j < N; j++) {
			cout << visited_e[j];
		}
		cout << endl;

		cout << reachable << endl;*/

		result.push_back(reachable);
	}

	return result;
}

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