Submission #92802

#	Time	Username	Problem	Language	Result	Execution time	Memory
92802		psmao	Werewolf (IOI18_werewolf)	C++14	0 / 100	171 ms	25180 KiB

werewolf

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

const int maxn = 3005;

bool f[maxn][2];
VI adj[maxn];
queue<pii> q;

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) {
  int Q = S.size(), M = X.size();
  std::vector<int> A(Q);
  if(N <= 3000)
  {
  	for(int i = 0; i < M; ++ i) 
  	{
  		adj[X[i]].pb(Y[i]);
  		adj[Y[i]].pb(X[i]);
  	}
  	for(int i = 0; i < Q; ++ i)
  	{
  		memset(f,false,sizeof(f));
  		f[S[i]][0] = true;
  		q.push(mp(S[i],0));
  		while(!q.empty())
  		{
  			int now = q.front().fi, form = q.front().se; q.pop();
  			if(form == 0) 
  			{
  				if(!f[now][1] && f[now][0] && now <= R[i] && now >= L[i])
  				{
  					f[now][1] = f[now][0];
  					q.push(mp(now,1));
  				}
  			}
  			for(auto nxt : adj[now])
  			{
  				if(form == 0) 
  				{
  					if(!f[nxt][0] && f[now][0] && nxt >= L[i])
  					{
  						f[nxt][0] = f[now][0]&(nxt>=L[i]);
  						q.push(mp(nxt, 0));
  					}
  				}
  				else 
				{
					if(!f[nxt][1] && f[now][1] && nxt<=R[i])
					{
						f[nxt][1] = f[now][1]&(nxt<=R[i]);
						q.push(mp(nxt, 1));
					}
				}
  			} 
  		}
  		A[i] = f[E[i]][1];
  		D("%d\n",f[E[i]][1]);
  	}
  }
  assert(0);
  return A;
}

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