Submission #127719

#	Time	Username	Problem	Language	Result	Execution time	Memory
127719		Shush	Werewolf (IOI18_werewolf)	C++17	15 / 100	4010 ms	50108 KiB

werewolf

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

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

bool dfs(int u, int w = 0){
//	cerr << u << " " << w << "\n";
	if(u == e[c] && w) return true;
	bool ans = false;
	v[u][w] = 1;
	for(int t : adj[u]){

		if(!v[t][w]){
			if(l[c] > t && !w) {
//				cerr << t << " invalid " << w << "\n";
				continue;
			}
			if(r[c] < t && w) {
//				cerr << t << " invalid " << w << "\n";
				continue;
			}
			if(l[c] <= t && r[c] >= t){
				if(!w)
				ans = ans || dfs(t, 0);
				ans = ans || dfs(t, 1);

			}
			else
			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 < m; 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<vector<int>>(n, vector<int> (2, 0));
		if(s[i] >= l[i] && s[i] <= r[i])
		a[i] = dfs(s[i]) || dfs(s[i], 1);
		else
		a[i] = dfs(s[i]);
	}
	return a;
}

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