제출 #765853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765853		sentheta	늑대인간 (IOI18_werewolf)	C++17	15 / 100	168 ms	21272 KiB

werewolf

#include "werewolf.h"
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 3005;

int n, m, q;
V<int> adj[N];

V<int> ans;

int l, r, tar;
bool vis[N][2];
bool dfs(int x,int t){
	// cout << x _ t << nl;
	if(t==1 && r<x) return 0;
	if(t==0 && x<l) return 0;
	if(vis[x][t]) return 0;
	vis[x][t] = 1;


	if(x==tar && t==1) return 1;
	if(t==0 && l<=x && x<=r && dfs(x,1)){
		return 1;
	}
	for(int y : adj[x]){
		if(dfs(y,t)) return 1;
	}
	return 0;
}

V<int> check_validity(int _n,V<int>_u, V<int>_v,
							V<int>_s, V<int>_e,V<int>_l,V<int>_r){
	n = _n; m = _u.size(); q = _s.size();
	ans = V<int>(q);

	rep(i,0,m){
		adj[_u[i]].push_back(_v[i]);
		adj[_v[i]].push_back(_u[i]);
	}

	rep(i,0,q){
		rep(x,0,n) rep(t,0,2) vis[x][t] = 0;

		l = _l[i];
		r = _r[i];
		tar = _e[i];
		ans[i] = dfs(_s[i], 0);
	}

	return ans;
}

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