Submission #138292

#	Time	Username	Problem	Language	Result	Execution time	Memory
138292		wilwxk	Werewolf (IOI18_werewolf)	C++14	0 / 100	4081 ms	30112 KiB

werewolf

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

const int MAXN=4e5+5;
vector<int> respf, g[MAXN];
int aresta[MAXN][2];
int n, m, q;

bool bfs(int ori, int dest, int l, int r) {
	int lobo[MAXN], homem[MAXN];
	memset(lobo, 0, sizeof(lobo));
	memset(homem, 0, sizeof(homem));
	if(ori<l) return 0;
	if(dest>r) return 0;
	homem[ori]=1;
	for(int i=0; i<2*n; i++) {
		for(int i=0; i<m; i++) {
		int a=aresta[i][0]; int b=aresta[i][1];
		if(homem[a]) {
			if(b>=l) homem[b]=1;
		}
		if(lobo[a]) {
			if(b<=r) lobo[b]=1;
		}
		if(homem[b]) {
			if(a>=l) homem[a]=1;
		}
		if(lobo[b]) {
			if(a<=r) lobo[a]=1;
		}
		if(homem[a]&&l<=a&&a<=r) lobo[a]=1;
		if(homem[b]&&l<=b&&b<=r) lobo[b]=1;
	}
	}
	
	return lobo[dest];
}	

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) {
  n=N; m=X.size();
  q=S.size();

  for(int i=0; i<m; i++) {
  	int a=X[i]; int b=Y[i];
  	g[a].push_back(b);
  	g[b].push_back(a);
  	aresta[i][0]=a;
  	aresta[i][1]=b;
  }


  for(int i=0; i<q; i++) {
  	int a=S[i]; int b=E[i];
  	int c=L[i]; int d=R[i];
  	printf("aadahb %d %d %d %d\n", a, b, c, d);
  	int val=bfs(a, b, c, d);
  	respf.push_back(val);
  }

  return respf;
}

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