Submission #127644

#	Time	Username	Problem	Language	Result	Execution time	Memory
127644		Shush	Werewolf (IOI18_werewolf)	C++17	0 / 100	4011 ms	39524 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

int n, m, q, c = 0;
vector<int> s, e, l, r, v, a;
vector<vector<int>>adj;

bool dfs(int u, int w = 0){
	if(u == e[c]) return true;
	bool ans = false;
	v[u] = 1;
	for(int t : adj[u]){
		if(!v[t]){
			if(l[c] > t && !w) continue;
			if(r[c] < t && w) continue;
			if(l[c] <= t && r[c] >= t){
				ans = ans || dfs(t, 1);
			}
			ans = ans || dfs(t, w);
		}
	}
	return ans;
}

vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
	n = N, m = X.size(), q =  S.size();
	adj = vector<vector<int>> (n);
	for(int i = 0; i < n; i++){
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	s = S, e = E, l = L, r = R;
	a = vector<int> (q);
	for(int i = 0; i < q; i++, c++){
		v = vector<int>(n, 0);
		a[i] = dfs(s[i]);
	}
	return a;
}

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