Submission #125782

#	Time	Username	Problem	Language	Result	Execution time	Memory
125782		arthurconmy	Werewolf (IOI18_werewolf)	C++14	15 / 100	4026 ms	32228 KiB

werewolf

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>

#ifndef ARTHUR_LOCAL
	#include "werewolf.h"
#endif

using namespace std;

using vi = vector<int>;

#define REP(i,a,b) \
for(int i=int(a); i<=int(b); i++)

#define pb push_back

const int MAXN = int(2e5)+1;
bool human_vis[MAXN];
bool wolf_vis[MAXN];
vi adj[MAXN];
bool works=false;
int l=-1;
int r=-1;

void human_dfs(int u)
{
	// cout << "HUMAN DFS AT " << u << endl;

	human_vis[u]=1;

	for(auto v:adj[u])
	{
		if(human_vis[v] || v < l) continue;
		human_dfs(v);
	}
}

void wolf_dfs(int u)
{
	wolf_vis[u]=1;

	if(works || human_vis[u])
	{
		works=1;
		return;
	}

	for(auto v:adj[u])
	{
		if(wolf_vis[v] || v > r) continue;
		wolf_dfs(v);
	}
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) 
{
 	int M = X.size();
 	int Q = S.size();

 	REP(i,0,M-1)
 	{
 		adj[X[i]].pb(Y[i]);
 		adj[Y[i]].pb(X[i]);
 	}

 	vi ans;

 	REP(q,0,Q-1)
 	{
 		REP(i,0,MAXN-1)
 		{
 			human_vis[i]=0;
 			wolf_vis[i]=0;
 		}

 		// cout << "DONE" << endl;

 		works=0;
 		l=L[q];
 		r=R[q];

 		human_dfs(S[q]);
 		wolf_dfs(E[q]);

 		if(works) ans.pb(1);
 		else ans.pb(0);
 	}

 	return ans;
}

// int main()
// {
// 	vi ans = check_validity(6,{5,1,1,3,3,5},{1,2,3,4,0,2},{4,4,5},{2,2,4},{1,2,3},{2,2,4});

// 	for(auto a:ans)
// 	{
// 		cout << a << " ";
// 	}
// 	cout << endl;
// }

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