Submission #425416

#	Time	Username	Problem	Language	Result	Execution time	Memory
425416		Monchito	Werewolf (IOI18_werewolf)	C++14	0 / 100	4073 ms	38664 KiB

werewolf

#include "werewolf.h"
#include <cstring>
using namespace std;
using vi = vector<int>;

#define sz(x) (int)x.size()

const int MAXN = 2e5;

vi G[MAXN];
bool vis[MAXN], can;
int s, e, l, r;

void DFS(int u, int t) {
	if(u == e) can = true;
	vis[u] = true;
	
	for(int v : G[u]) {
		if(!vis[v]) {
			if(t == 0){
				if(v >= l) DFS(v, t);
				else if(v <= r && u <= r) DFS(v, 1);
			} else {
				if(v <= r) DFS(v, t);
			}
		}	
	}
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	for(int i=0; i<sz(X); i++) {
		int u = X[i], v = Y[i];
		G[u].push_back(v);
		G[v].push_back(u);
	}

	int Q = sz(S);
	vi ret(Q);

	for(int i=0; i<Q; i++) {
		s = S[i]; e = E[i]; l = L[i]; r = R[i];
		can = false;
		memset(vis, false, sizeof(vis));

		DFS(s, 0);
		ret[i] = (can)? 1 : 0;
	}

	return ret;
}

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