oj.uz

답안 #604070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
604070 2022-07-24T16:52:42 Z SOOS 늑대인간 (IOI18_werewolf) C++14
0 / 100
 127 ms 28124 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 127 ms 28124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -