Submission #212630

#	Time	Username	Problem	Language	Result	Execution time	Memory
212630		MarcoMeijer	Werewolf (IOI18_werewolf)	C++14	15 / 100	424 ms	28256 KiB

werewolf

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

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MX=6000;

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	bitset<MX> visited[2];
	vi adj[MX];

	int M = X.size();
	RE(i,M) {
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}

	int Q = S.size();
	vi A(Q);
	RE(i,Q) {
		RE(j,2) visited[j].reset();
		queue<ii> q; q.push({S[i],0}); visited[0][S[i]]=1;
		while(!q.empty()) {
			ii p = q.front(); q.pop();
			int u = p.fi;
			int w = p.se;
			for(int v : adj[u]) {
				if(visited[w][v] ) continue;
				if(!w && v < L[i]) continue;
				if( w && v > R[i]) continue;
				visited[w][v] = 1;
				q.push({v,w});
			}
			if(!visited[1][u] && L[i] <= u && u <= R[i]) {
				visited[1][u] = 1;
				q.push({u,1});
			}
		}
		A[i] = visited[1][E[i]];
	}

	return A;
}

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