Submission #602367

#	Time	Username	Problem	Language	Result	Execution time	Memory
602367		jairRS	Werewolf (IOI18_werewolf)	C++17	15 / 100	1134 ms	524288 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
 
const int INF = 1e9;
 
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R)
{
	vvi adj = vvi(N);
	vvi highestOnPath = vvi(N, vi(N, INF));
	for (int i = 0; i < (int)X.size(); i++)
	{
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
 
	priority_queue<pii, vector<pii>, greater<pii>> pqueue;
 
	for (int i = 0; i < N; i++)
	{
		pqueue.push({i, i});
		highestOnPath[i][i] = i;
 
		while (!pqueue.empty())
		{
			pii cur = pqueue.top();
			int curNode = cur.second;
			int curMax = cur.first;
			pqueue.pop();
			if (curMax > highestOnPath[i][curNode])
				continue;
			for (int a : adj[curNode])
				if (max(curMax, a) < highestOnPath[i][a])
				{
					highestOnPath[i][a] = max(curMax, a);
					pqueue.push({highestOnPath[i][a], a});
				}
		}
	}
 
	int Q = S.size();
	vi ans(Q);
	for (int i = 0; i < Q; i++)
	{
		vector<int> visited(N, false);
		queue<int> queue;
		queue.push(S[i]);
		visited[S[i]] = true;
 
		while (!queue.empty())
		{
			int cur = queue.front();
			queue.pop();
			if (cur < L[i])
				continue;
			if (highestOnPath[cur][E[i]] <= R[i])
				ans[i] = 1;
 
			for (int a : adj[cur])
			{
				if (visited[a])
					continue;
				queue.push(a);
				visited[a] = true;
			}
		}
	}
 
	return ans;
}

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