Submission #261419

#	Time	Username	Problem	Language	Result	Execution time	Memory
261419		youssefbou62	Werewolf (IOI18_werewolf)	C++14	15 / 100	279 ms	19704 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){
	if(u>x)return ; 
	visited0[u] = 1 ; 
	for(int v : adj[u]){
		if( !visited0[v] ){
			dfs0(v,x); 
		}
	}
}

void dfs1(int u,int x){
	if(u<x)return ; 

	visited1[u] = 1 ; 
	for(int v : adj[u]){
		if( !visited1[v] ){
			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) ; 
	
	dfs0(E[i],R[i]);
    dfs1(S[i],L[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: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51