QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#17920#2213. Knightqingyu_orzWA 289ms61332kbC++141.2kb2022-01-15 12:15:222022-05-04 16:20:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 16:20:33]
  • 评测
  • 测评结果:WA
  • 用时:289ms
  • 内存:61332kb
  • [2022-01-15 12:15:22]
  • 提交

answer

#include<bits/stdc++.h>
#define mk(x,y) ((x-1)*m+y)
using namespace std;
char s[1005][1005];
vector<int>g[1000005];
int mb[8][2];
int col[1000005];
void dfs(int x){
	for(auto cu:g[x]){
		if(col[cu])continue;
		col[cu]=-col[x];
		dfs(cu);
	}
}
int main(){
	int n,m,x,y;
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
	mb[0][0]=x,mb[0][1]=y;
	mb[1][0]=-x,mb[1][1]=y;
	mb[2][0]=x,mb[2][1]=-y;
	mb[3][0]=-x,mb[3][1]=-y;
	mb[4][0]=y,mb[4][1]=x;
	mb[5][0]=-y,mb[5][1]=x;
	mb[6][0]=y,mb[6][1]=-x;
	mb[7][0]=-y,mb[7][1]=-x;
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
		if(s[i][j]!='@'){
			for(int k=0;k<8;++k){
				int dx=i+mb[k][0],dy=j+mb[k][1];
				if(dx<1||dy<1||dx>n||dy>m)continue;
				if(s[dx][dy]=='@')continue;
				int u=mk(i,j),v=mk(dx,dy);
				g[u].emplace_back(v);
				g[v].emplace_back(u);
			}
		}
	int A=-1,B=-1;
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
		if(s[i][j]=='A')A=mk(i,j);
		else if(s[i][j]=='B')B=mk(i,j);
	}
	if(!g[A].size()){
		puts("Bob");
		return 0;
	}
	int N=mk(n,m);
	for(int i=1;i<=N;++i)if(!col[i]){
		col[i]=i;
		dfs(i);
	}
	if(abs(col[A])!=abs(col[B]))puts("Alice");
	else if(col[A]!=col[B])puts("Alice");
	else puts("Bob");
	return 0;
}

Details

Test #1:

score: 100
Accepted
time: 67ms
memory: 43100kb

Test #2:

score: 0
Accepted
time: 6ms
memory: 28356kb

Test #3:

score: 0
Accepted
time: 289ms
memory: 61332kb

Test #4:

score: -100
Wrong Answer
time: 124ms
memory: 44584kb