Submission #1135331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135331		alterio	Werewolf (IOI18_werewolf)	C++20	0 / 100	80 ms	10564 KiB

werewolf

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

using namespace std;

const int mxn = 3e3 + 10;

vector<int> g[mxn];

struct State {
	int pos, lastT;
	bool transform;
};

bool pos(int start, int end, int l, int r) {
	if (start < l) return 0;
	bool visited[mxn];
	memset(visited, 0, sizeof(visited));
	queue<State> q;
	q.push({start, (start <= r), 0});
	visited[start] = 1;
	while (q.size()) {
		auto cur = q.front();
		q.pop();
		if (cur.pos == end) {
			return (cur.transform || cur.lastT);
		}
		for (auto x : g[cur.pos]) {
			if (!visited[x]) {
				if (cur.transform) {
					if (x <= r) {
						visited[x] = 1;
						q.push({x, 0, 1});
					}
				}
				else {
					if (x >= l) {
						visited[x] = 1;
						if (x <= r) q.push({x, 1, 0});
						else q.push({x, 0, 0});
					}
					else {
						if (cur.lastT) {
							q.push({x, 0, 1});
							visited[x] = 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);
	for (int i = 0; i < N - 1; i++) {
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}
	for (int i = 0; i < Q; i++) {
		A[i] = pos(S[i], E[i], L[i], R[i]);
	}
    return A;
}

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