Submission #115806

#	Time	Username	Problem	Language	Result	Execution time	Memory
115806		Mahdi_Jfri	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	417 ms	8312 KiB

coprobber

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

#define ll long long
#define pb push_back

using namespace std;

const int maxn = 5e2 + 20;

int vertex;

int par[maxn][maxn] , d[maxn][maxn];

bool visited[maxn][maxn][2];

vector<int> adj[maxn];

int start(int n, bool A[MAX_N][MAX_N])
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(A[i][j])
				adj[i].pb(j);

	queue<pair<pair<int , int> , bool> > q;

	for(int i = 0; i < n; i++)
		q.push({{i , i} , 0}) , q.push({{i , i} , 1}) , visited[i][i][0] = visited[i][i][1] = 1;

	while(!q.empty())
	{
		int v = q.front().first.first , u = q.front().first.second;
		bool x = q.front().second;
		q.pop();

		if(x)
		{
			for(auto w : adj[v])
				if(!visited[w][u][0])
				{
					par[w][u] = v;
					q.push({{w , u} , 0});
					visited[w][u][0] = 1;
				}

			if(!visited[v][u][0])
			{
				par[v][u] = v;
				q.push({{v , u} , 0});
				visited[v][u][0] = 1;
			}
		}
		else
		{
			for(auto w : adj[u])
			{
				d[v][w]++;
				if(d[v][w] == (int)adj[w].size())
				{
					visited[v][w][1] = 1;
					q.push({{v , w} , 1});
				}
			}
		}
	}

	for(int i = 0; i < n; i++)
	{
		int t = 0;
		for(int j = 0; j < n; j++)
			t += visited[i][j][0];
		if(t == n)
		{
			vertex = i;
			return i;
		}
	}

    return -1;
}

int nextMove(int R)
{
	vertex = par[vertex][R];
    return vertex;
}

• Subtask 1: 16 / 16
• Subtask 2: 14 / 14
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40