Submission #134251

#	Time	Username	Problem	Language	Result	Execution time	Memory
134251		MoNsTeR_CuBe	Werewolf (IOI18_werewolf)	C++17	15 / 100	4045 ms	21664 KiB

werewolf

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

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 Q = S.size();
	int M = X.size();
	
	vector< vector< int > > Graph(N);
	
	for(int i = 0; i < M; i++){
		Graph[X[i]].push_back(Y[i]);
		Graph[Y[i]].push_back(X[i]);
	}
	
	vector<int> A(Q);
	
		
		for(int j = 0; j < Q; j++){
			vector< bool > Human(N, false);
		
			if(S[j] < L[j] || E[j] > R[j]){
				A[j] = 0;
				continue;
			}
		
			queue< int > q;
			q.push(S[j]);
			Human[S[j]] = true;
			
			while(!q.empty()){
				int node = q.front();
				q.pop();
				
				for(int neighbours : Graph[node]){
					if(Human[neighbours]) continue;
					if(neighbours < L[j]) continue;
					Human[neighbours] = true;
					q.push(neighbours);
				}
			}
			
			q.push(E[j]);
			
			vector< bool > visited(N, false);
			visited[E[j]] = true;
			
			while(!q.empty()){
				int node = q.front();
				q.pop();
				
				for(int neigh : Graph[node]){
					if(neigh > R[j] || visited[neigh]){
						continue;
					}
					visited[neigh] = true;
					q.push(neigh);
				}
			}
			bool verif = false;
			for(int i = 0; i < N; i++){
				if(Human[i] && visited[i]){
					A[j] = 1;
					verif = true;
					break;
				}
			}
			if(!verif) A[j] = 0;
		}
		
		return A;
}

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