제출 #1159274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159274		Gr1sen	늑대인간 (IOI18_werewolf)	C++20	15 / 100	4094 ms	22408 KiB

werewolf

#include "werewolf.h"
#include<iostream>
#include<queue>

using namespace std;

#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define qq queue<pi>
#define ti tuple<int, int>
//#define G(a, b) get<a>(b)

vvi Adj;

bool oink(int a, int b, int l, int r) {
	vi M(Adj.size(), 0);
	if (a == b) return 1;
	qq Q;
	Q.push({a, 1});
	Q.push({b, 2});
	while (!Q.empty()) {
		int c = Q.front().first, d = Q.front().second;
		Q.pop();
		if (d == 1 && c < l) continue;
		if (d == 2 && c > r) continue;
		if (M[c] != 0) {
			if (M[c] == d) continue;
			return 1;
		}
		M[c] = d;
		for (auto i : Adj[c]) {
			Q.push({i, d});
		}
	}
	return 0;
}

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 Q = S.size();
  Adj = vvi(N);
  //cerr << "Adj start" << endl;
  for (int i = 0; i < X.size(); i++) {
	Adj[X[i]].push_back(Y[i]);
	Adj[Y[i]].push_back(X[i]);
  }
  //cerr << "Adj end" << endl;
  vector<int> A(Q);
  for (int i = 0; i < Q; ++i) {
    A[i] = oink(S[i], E[i], L[i], R[i]);
  }
  return A;
}

/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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