Submission #294164

#	Time	Username	Problem	Language	Result	Execution time	Memory
294164		TheRedstar	Werewolf (IOI18_werewolf)	C++14	15 / 100	4032 ms	31480 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>


using namespace std;

typedef vector<int> vi;


struct city {
	vi con;
	bool visited_normal=false;
	bool visited_werewolf=false;
};


vector<city> cities;


vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	int Q = S.size();
	int M = X.size();
	
	cities.resize(N);
	
	
	for(int m=0; m<M; m++) {
		cities[X[m]].con.push_back(Y[m]);
		cities[Y[m]].con.push_back(X[m]);
	}
	
	vi A(Q,0);
	
	for (int i = 0; i < Q; ++i) {
		/*if(S[i]<L[i] or E[i]>R[i]) { //impossible
			//A[i] = 0;
			continue;
		}*/
		queue<pair<int,bool>> bfs;
		bfs.push({S[i],false});
		
		while(!bfs.empty()) {
			int c;
			bool ww;
			tie(c,ww)=bfs.front();
			bfs.pop();
			
			if(c==E[i]) {
				A[i]=1;
				break;
			}
			
			if(ww and cities[c].visited_werewolf) continue;
			if(!ww and cities[c].visited_normal) continue;
			
			bool transform=false;
			if(!ww and c<=R[i] and !cities[c].visited_werewolf) transform=true;
			
			if(!ww) cities[c].visited_normal=true;
			if(ww or transform) cities[c].visited_werewolf=true;
			
			for(int other:cities[c].con) {
				if(!ww and other>=L[i] and !cities[other].visited_normal) bfs.push({other,false});
				if((ww or transform) and other<=R[i] and !cities[other].visited_werewolf) bfs.push({other,true});
			}
			
		}
		for(int n=0; n<N; n++) cities[n].visited_normal=cities[n].visited_werewolf=false;
		
		//A[i] = 0;
	}
	return A;
}

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