Submission #114094

#	Time	Username	Problem	Language	Result	Execution time	Memory
114094		antimirage	Werewolf (IOI18_werewolf)	C++14	15 / 100	307 ms	49676 KiB

werewolf

#include "werewolf.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

vector < vector <int> > g;

const int N = 3005;

int n, m, u[2][N];

void dfs (int v, int type, int l, int r)
{
	u[type][v] = 1;
	
	for (auto to : g[v])
	{
		if (u[type][to] || to < l || to > r) continue;
		
		dfs(to, type, l, r);	
	}
}

vector<int> check_validity(int N, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) 
{
	n = N;
	m = x.size();
	g.resize(n + 1);
	
	for (int i = 0; i < m; i++)
		g[ x[i] ].pb( y[i] ),
		g[ y[i] ].pb( x[i] );
	
	int q = s.size();
	
	vector <int> ans;
	
	for (int i = 0; i < q; i++)
	{
		memset(u, 0, sizeof(u));
		
		dfs(s[i], 0, l[i], n - 1);
		dfs(e[i], 1, 0, r[i]);
		
		bool fl = 0;
		
		for (int j = 0; j < n; j++){
		
			if (u[0][j] && u[1][j])
				fl = 1;
		}
		ans.pb(fl);
	}
	return ans;
}

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