Submission #817256

#	Time	Username	Problem	Language	Result	Execution time	Memory
817256		Dan4Life	Werewolf (IOI18_werewolf)	C++17	15 / 100	189 ms	38972 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using vi = vector<int>;
const int mxN = (int)2e5+10;
int n, m, q;
bool vis[mxN];
vi adj[mxN];

bool dfs(int s, int t, int l, int r){
	vis[s] = 1; if(s==t) return 1;
	for(auto u : adj[s]){
		if(vis[u]) continue;
		if(u<n and u<l) continue;
		if(u>=n and u-n>r) continue;
		if(s>=n and u<n) continue; 
		if(dfs(u,t,l,r)) return 1;
	}
	return false;
}

vi check_validity(int N, vi U, vi V, vi S, vi T, vi L, vi R) {
	n = N, m = sz(U), q = sz(S); vi ans(q, 0);
	for(int i = 0; i < m; i++){
		int a = U[i], b = V[i];
		adj[a].pb(b); adj[b].pb(a); a+=n, b+=n;
		adj[a].pb(b); adj[b].pb(a); a-=n, b-=n;
		adj[a].pb(a+n); adj[b].pb(b+n);
	}
	for(int i = 0; i < q; i++){
		fill(vis,vis+2*n,0);
		ans[i] = dfs(S[i],T[i]+n,L[i],R[i]);
	}
	return ans;
}

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