Submission #261414

#	Time	Username	Problem	Language	Result	Execution time	Memory
261414		youssefbou62	Werewolf (IOI18_werewolf)	C++14	0 / 100	227 ms	28024 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

#define sz(x)	(int)x.size()
#define pb push_back 

using namespace std; 

const int MAXN = 3005 ; 
bool visited0[MAXN] , visited1[MAXN] ; 
vector<int> adj[MAXN] ; 
void dfs0(int u,int x){
	visited0[u] = 1 ; 
	for(int v : adj[u]){
		if( !visited0[v] && v <= x){
			dfs0(v,x); 
		}
	}
}

void dfs1(int u,int x){
	visited1[u] = 1 ; 
	for(int v : adj[u]){
		if( !visited1[v] && v >= x){
			dfs1(v,x); 
		}
	}
}

vector<int> check_validity(int N,
	vector<int> X,
	vector<int> Y,
    vector<int> S, 
    vector<int> E,
    vector<int> L, 
    vector<int> R) {
	int M = sz(X); 
	for(int i = 0 ; i < M ; i++ ){
		adj[X[i]].pb(Y[i]); 
		adj[Y[i]].pb(X[i]); 
	}

  int Q =sz(S);
  vector<int> A(Q);
  for (int i = 0; i < Q; ++i) {
    A[i] = 0 ;
	memset(visited1,0,sizeof visited1) ; 
	memset(visited0,0,sizeof visited0) ; 
	if(E[i]<=R[i])
	dfs0(E[i],R[i]);
	else 
    dfs1(E[i],L[i]); 
    if(E[i]>=L[i])
    dfs1(S[i],L[i]);
    else   
    dfs0(S[i],R[i]); 
    for(int j = L[i] ;j <= R[i];j++)
    	A[i]|= (visited0[j]&&visited1[j]); 
  
  }
  return A;
}


// namespace {

// int read_int() {
//   int x;
//   if (scanf("%d", &x) != 1) {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return x;
// }

// }  // namespace

// int main() {
//   int N = read_int();
//   int M = read_int();
//   int Q = read_int();
//   std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
//   for (int j = 0; j < M; ++j) {
//     X[j] = read_int();
//     Y[j] = read_int();
//   }
//   for (int i = 0; i < Q; ++i) {
//     S[i] = read_int();
//     E[i] = read_int();
//     L[i] = read_int();
//     R[i] = read_int();
//   }

//   std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
//   for (size_t i = 0; i < A.size(); ++i) {
//     printf("%d\n", A[i]);
//   }
//   return 0;
// }

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