Submission #113017

#	Time	Username	Problem	Language	Result	Execution time	Memory
113017		arman_ferdous	Werewolf (IOI18_werewolf)	C++17	0 / 100	171 ms	23144 KiB

werewolf

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

const int N = 3010;

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

int l, r;
int vis[2][N];
void dfs(int u, int werewolf) {
	if((!werewolf && u < l) || (werewolf && r < u)) return;
	vis[werewolf][u] = 1;
	for(auto e : g[werewolf][u]) if(!vis[e.first][e.second]) {
		if(!werewolf && e.first)
			if(r < u) continue;
		dfs(e.second, e.first);
	}
}

vector<int> ans;
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[0][X[i]].push_back({0, Y[i]});
		g[0][Y[i]].push_back({0, X[i]});
		g[0][X[i]].push_back({1, Y[i]});
		g[0][Y[i]].push_back({1, X[i]});
		g[1][X[i]].push_back({1, Y[i]});
		g[1][Y[i]].push_back({1, X[i]});
	}

	for(int i = 0; i < q; i++) {
		for(int u = 0; u < n; u++)
			vis[0][u] = vis[1][u] = 0;
		l = L[i], r = R[i];

		dfs(S[i], 0);
		if(vis[1][E[i]]) ans.push_back(1);
		else ans.push_back(0);
	}
	return ans;
}

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