Submission #139926

#	Time	Username	Problem	Language	Result	Execution time	Memory
139926		vince	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4066 ms	33148 KiB

werewolf

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <queue>
#include <set>
#include <stack>

using namespace std;

#define long long long
#define fi first
#define se second
typedef pair<int,int> ii;


int n, m, q;
bool visited[200003][2];
vector<int> vec[200003];

int qua(int u, int l, int r)
{
	if(u < l) return 1;
	else if(l <= u && u <= r) return 2;
	else return 3;
}

void dfs(int u, int x, int l, int r)
{
	// printf("%d %d %d %d\n", u, x, l, r);
	visited[u][x] = 1;
	if(x == 0 && !visited[u][1] && l <= u && u <= r)
		dfs(u,1, l, r);
	
	for(int v : vec[u])
	{
		if(x == 0 && v >= l && !visited[v][0])
			dfs(v,0, l, r);
		if(x == 1 && v <= r && !visited[v][1])
			dfs(v,1, 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();
  	q = S.size();
  	for(int i = 0; i < m; i++)
  	{
  		vec[X[i]].push_back(Y[i]);
  		vec[Y[i]].push_back(X[i]);
  	}
  	vector<int> ans;
  	for(int i = 0; i < q; i++)
  	{
  		for(int j = 0; j < n; j++)
  			visited[j][0] = visited[j][1] = 0;

  		dfs(S[i], 0, L[i], R[i]);
  		ans.push_back(visited[E[i]][1]);
  
  	}
	return ans;
}

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