Submission #1135344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135344		alterio	Werewolf (IOI18_werewolf)	C++20	0 / 100	79 ms	9796 KiB

werewolf

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

using namespace std;

const int mxn = 3e3 + 10;

vector<int> g[mxn];

bool pos(int start, int end, int l, int r) {
	bool visitedH[mxn], visitedW[mxn];
	memset(visitedH, 0, sizeof(visitedH));
	memset(visitedW, 0, sizeof(visitedW));
	queue<int> q;
	q.push(start);
	visitedH[start] = 1;
	while (q.size()) {
		int pos = q.front();
		q.pop();
		for (auto x : g[pos]) {
			if (!visitedH[x] && x >= l) {
				visitedH[x] = 1;
				q.push(x);
			}
		}
	}
	q.push(end);
	visitedW[end] = 1;
	while (q.size()) {
		int pos = q.front();
		q.pop();
		if (visitedH[pos]) return 1;
		for (auto x : g[pos]) {
			if (!visitedW[x] && x <= r) {
				visitedW[x] = 1;
				q.push(x);
			}
		}
	}
	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) {
	for (int i = 0; i < N; i++) g[i].clear();
    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