Submission #340253

#	Time	Username	Problem	Language	Result	Execution time	Memory
340253		ogibogi2004	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	1067 ms	12652 KiB

coprobber

#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
/*
0-cop
1-robber
*/
int wl[MAX_N][MAX_N][2],cpos;
pair<pair<int,int>,int> nextMove1[MAX_N][MAX_N][2];
//vector<pair<pair<int,int>,bool> > g[MAX_N][MAX_N][2];
//vector<pair<pair<int,int>,bool> > g1[MAX_N][MAX_N][2];
int start(int n, bool a[MAX_N][MAX_N])
{
	for(int c=0;c<n;c++)
	{
		for(int r=0;r<n;r++)
		{
			for(int turn=0;turn<=1;turn++)
			{
				if(turn==0)
				{
					wl[c][r][turn]=1;
					for(int i=0;i<n;i++)
					{
						if(i==c||a[i][c])
						{
						//	g[c][r][(bool)turn].push_back({{i,r},(bool)1-turn});
							//g1[i][r][(bool)1-turn].push_back({{c,r},(bool)turn});
						}
					}
				}
				else
				{
					for(int i=0;i<n;i++)
					{
						if(a[i][r])
						{
							//g[c][r][turn].push_back({{c,i},1-turn});
							//g1[c][i][1-turn].push_back({{c,r},turn});
							++wl[c][r][turn];
						}
					}
				}
				if(c==r)wl[c][r][turn]=0;
			}
		}
	}
	queue<pair<pair<int,int>,int> >q;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			for(int turn=0;turn<2;turn++)
			{
				if(wl[i][j][turn]==0)q.push({{i,j},turn});
			}
		}
	}
	pair<pair<int,int>,int>v;
	while(!q.empty())
	{
		pair<pair<int,int>,int> u=q.front();q.pop();
		if(u.second==1)
		{
			for(int i=0;i<n;i++)
			{
				if(i==u.first.first||a[u.first.first][i])
				{
					v={{i,u.first.second},1-u.second};
					--wl[v.first.first][v.first.second][v.second];
					if(wl[v.first.first][v.first.second][v.second]==0)
					{
						nextMove1[v.first.first][v.first.second][v.second]=u;
						q.push(v);
					}
				}
			}
		}
		else
		{
			for(int i=0;i<n;i++)
			{
				if(a[u.first.second][i])
				{
					v={{u.first.first,i},1-u.second};
					--wl[v.first.first][v.first.second][v.second];
					if(wl[v.first.first][v.first.second][v.second]==0)
					{
						nextMove1[v.first.first][v.first.second][v.second]=u;
						q.push(v);
					}
				}
			}
		}
		/*for(auto v:g1[u.first.first][u.first.second][u.second])
		{
			--wl[v.first.first][v.first.second][v.second];
			if(wl[v.first.first][v.first.second][v.second]==0)
			{
				nextMove1[v.first.first][v.first.second][v.second]=u;
				q.push(v);
			}
		}*/
	}
	for(int i=0;i<n;i++)
	{
		bool ok=1;
		for(int j=0;j<n;j++)
		{
			if(wl[i][j][1]>0)ok=0;
		}
		if(ok)
		{
			cpos=i;
			return i;
		}
	}
	return -1;
}
int nextMove(int R)
{
	pair<pair<int,int>,int> gg=nextMove1[cpos][R][0];
	cpos=gg.first.first;
    return cpos;
}

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