Submission #84855

#	Time	Username	Problem	Language	Result	Execution time	Memory
84855		SirCeness	Werewolf (IOI18_werewolf)	C++14	0 / 100	208 ms	28236 KiB

werewolf

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

using namespace std;

void dfsup(int node, list<int> *adj, int edge, int addedge, bool *visited, int *arr, int arri){
	visited[node] = true;
	if (node >= addedge) arr[arri++] = node;
	for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it){
		if (visited[*it]) continue;
		if (*it < edge) continue;
		dfsup(*it, adj, edge, addedge, visited, arr, arri);
	}
}

void dfsdown(int node, list<int> *adj, int edge, int addedge, bool *visited, int *arr, int arri){
	visited[node] = true;
	if (node <= addedge) arr[arri++] = node;
	for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it){
		if (visited[*it]) continue;
		if (*it > edge) continue;
		dfsup(*it, adj, edge, addedge, visited, arr, arri);
	}
}

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();
	vector<int> A(Q);
	
	list<int> *adj;
	for (int i = 0; i < (int)X.size(); i++){
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	
	for (int i = 0; i < Q; i++){
		int l = L[i];
		int r = R[i];
		int s = S[i];
		int e = E[i];
		
		int arr1[N];
		int arr2[N];
		int arr1i = 0;
		int arr2i = 0;
		
		bool visited[N];
		
		for (int q = 0; q < N; q++) visited[q] = false;
		dfsup(s, adj, l, r, visited, arr1, arr1i);
		for (int q = 0; q < N; q++) visited[q] = false;
		dfsdown(e, adj, r, l, visited, arr2, arr2i);
		
		sort(arr1, arr1+arr1i);
		sort(arr2, arr2+arr2i);
		int a = 0, b = 0;
		bool ret = false;
		while (a < arr1i && b < arr2i){
			if (arr1[a] == arr2[b]){
				ret = true;
				break;
			} else if (arr1[a] < arr2[b]) a++;
			else b++;
		}
		A[i] = ret;
	}
	
	return A;
}

/*
	vector<int> A(Q);
	for (int i = 0; i < Q; ++i) {
		A[i] = 0;
	}	
	return A;
*/

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:35:22: warning: 'adj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   adj[X[i]].push_back(Y[i]);
   ~~~~~~~~~~~~~~~~~~~^~~~~~

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