Submission #85354

#	Time	Username	Problem	Language	Result	Execution time	Memory
85354		SirCeness	Werewolf (IOI18_werewolf)	C++14	15 / 100	4021 ms	36488 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
 
using namespace std;
 
void dfsup(int node, list<int> *adj, int edge , int *visited){
	//cout << "dfsup(" << node << ")" << endl;
	visited[node] = 1;
	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, visited);
	}
}
 
int dfsdown(int node, list<int> *adj, int edge, int *visited){
	//cout << "dfsdown(" << node << ")" << endl;
	visited[node] = 2;
	for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it){
		if (*it > edge) continue;
		if (visited[*it] == 1) return 1;
		if (visited[*it]) continue;
		if (dfsdown(*it, adj, edge, visited)) return 1;
	}
	return 0;
}
 
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[N];
	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];
		
		/*cout << "l: " << l;
		cout << " r: " << r;
		cout << " s: " << s;
		cout << " e: " << e;
		cout << endl;*/
		
		int visited[N];
		
		for (int q = 0; q < N; q++) visited[q] = 0;
		dfsup(s, adj, l, visited);
		int a = (visited[e] == 1) ? 1 : dfsdown(e, adj, r, visited);
		
		A[i] = a;
	}
	
	return A;
}
 
/*
	vector<int> A(Q);
	for (int i = 0; i < Q; ++i) {
		A[i] = 0;
	}	
	return A;
*/

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