QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53307#2213. KnightSilent_AshRE 8ms6172kbC++2.4kb2022-10-04 21:37:492022-10-04 21:37:51

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-04 21:37:51]
  • 评测
  • 测评结果:RE
  • 用时:8ms
  • 内存:6172kb
  • [2022-10-04 21:37:49]
  • 提交

answer

#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e3 + 5 ;
const int M = 1e6 + 5 ;

int rd()
{
	int res = 0 , f = 1 ;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')f = -1 ; ch = getchar() ;}
	while(ch >= '0' && ch <= '9')res = (res << 1) + (res << 3) + (ch ^ 48) , ch = getchar() ;
	return res * f ;
}

struct Edge
{
	int from , to , w , next_ ;
	Edge(){}
	Edge(int a , int b , int c , int d):from(a),to(b),w(c),next_(d){} ;
} ;
Edge edge[M << 1] ;
int head[M << 1] , size_ ;
void add_(int from , int to , int w)
{
	edge[++size_] = Edge(from , to , w , head[from]) ;
	head[from] = size_ ;
}
void clear()
{
	memset(head , 0 , sizeof head) ;
	size_ = 0 ;
}

int mp[N][N] ;
int n , m , c , r ;
char s[N] ;
pair<int , int> A , B ;


int cl[M] , col = 2 ;

void dfs(int u , int col)
{
	if(cl[u]) return ;
	cl[u] = col ;
	for(int i = head[u] ; i ; i = edge[i].next_)
	{
		int v = edge[i].to ;
		dfs(v , col ^ 1) ;
	}
}

int main()
{
	n = rd() ; m = rd() ; c = rd() ; r = rd() ;
	int dx[] = {c , -c , c , -c , r , -r , r , -r} ;
	int dy[] = {r , -r , -r , r , c , -c , -c , c} ;
	
	for(int i = 1 ; i <= n ; i++)
	{
		scanf("%s" , s + 1) ;
		for(int j = 1 ; j <= m ; j++)
		{
			if(s[j] == '@') mp[i][j] = 0 ;
			else mp[i][j] = 1 ;
			if(s[j] == 'A') A = {i , j} ;
			else if(s[j] == 'B') B = {i , j} ;
		}
	}
	int f = 1 ;
	for(int t = 0 ; t < 8 ; t++)
		{
			int tx = dx[t] + A.first , ty = dy[t] + A.second ;
			if(tx < 0 || ty < 0 || tx > n || ty > m || !mp[tx][ty]) continue ;
			f = 0 ; break ;
		}
	if(f){cout << "Bob\n" ; return 0 ;}
	for(int i = 1 ; i <= n ; i++)
		for(int j = 1 ; j <= m ; j++)
		if(mp[i][j]) for(int id = (i - 1) * n + j , t = 0 ; t < 8 ; t++)
		{
			int tx = dx[t] + i  , ty = dy[t] + j ;
			if(tx < 0 || ty < 0 || tx > n || ty > m || !mp[tx][ty]) continue ;
			int to = (tx - 1) * n + ty ;
			add_(id , to , 0) ; add_(to , id , 0) ;
		}
	for(int i = 1 ; i <= n ; i++)
		for(int j = 1 ; j <= m ; j++)
  		{
		  	int id = (i - 1) * n + j ;
		  	if(!cl[id]) dfs(id , col) , col += 2 ;
		}
		
	if((cl[(A.first - 1) * n + A.second] ^ 1) != (cl[(B.first - 1) * n + B.second] ^ 1)) cout << "Alice\n" ;
	else cout << "Bob\n" ;
	return 0 ;
}


Details

Test #1:

score: 100
Accepted
time: 8ms
memory: 6172kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 4536kb

Test #3:

score: -100
Runtime Error