Submission #113018

#	Time	Username	Problem	Language	Result	Execution time	Memory
113018		arman_ferdous	Werewolf (IOI18_werewolf)	C++17	15 / 100	309 ms	19576 KiB

werewolf

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

const int N = 3010;

int n, m, q;
vector<int> g[N];
vector<int> ans;

bitset<N> human, werewolf;
void dfs1(int u, int l) {
	if(u < l) return;
	human[u] = 1;
	for(int v : g[u]) if(human[v] == 0)
		dfs1(v, l);
}
void dfs2(int u, int r) {
	if(r < u) return;
	werewolf[u] = 1;
	for(int v : g[u]) if(werewolf[v] == 0)
		dfs2(v, r);
}

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) {
	n = _n;
	m = X.size();
	q = S.size();

	for(int i = 0; i < m; i++) {
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}

	for(int i = 0; i < q; i++) {
		human = werewolf = 0;
		dfs1(S[i], L[i]);
		dfs2(E[i], R[i]);
		if((human & werewolf) != 0)
			ans.push_back(1);
		else ans.push_back(0);
	}
	return ans;
}

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