oj.uz

Submission #92802

# Submission time Handle Problem Language Result Execution time Memory
92802 2019-01-05T03:47:18 Z psmao Werewolf (IOI18_werewolf) C++14
0 / 100
 171 ms 25180 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 171 ms 25180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -