QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#65970#3039. Cleaninggyh20WA 16ms105244kbC++141.9kb2022-12-04 19:59:252022-12-04 19:59:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-04 19:59:27]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:105244kb
  • [2022-12-04 19:59:25]
  • 提交

answer

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
int n,m,q,bl[1000002],dfn[1000002],low[1000002],blk,tim,siz[1000002],fa[1000002],stk[1000002],tp,sz[1000002],dep[1000002];
char s[1002][1002],ist[1000002],v[1000002];
vector<int>A[1000002],B[1000002];
map<int,int>V[1000002];
inline int Pos(re int x,re int y){return (x-1)*m+y;}
inline void Add(re int x,re int y){A[x].push_back(y);}
inline void Add1(re int x,re int y){
	if(V[x].count(y))return;
	V[x][y]=1,B[x].push_back(y);
	printf("SSS%d %d\n",x,y);
}
inline void tj(re int x){
	dfn[x]=low[x]=++tim,stk[++tp]=x,ist[x]=1;
	for(auto z:A[x])
		if(!dfn[z])tj(z),low[x]=min(low[x],low[z]);
		else if(ist[z])low[x]=min(low[x],dfn[z]);
	if(low[x]==dfn[x]){
		++blk;
		do{
			bl[stk[tp]]=blk,ist[stk[tp]]=0;
			++sz[blk];
		}while(stk[tp--]^x);
	}
}
inline void dfs(re int x){
	dfn[x]=++tim,siz[x]=1,dep[x]+=sz[x],v[x]=1;
	for(auto z:B[x])fa[z]=x,dep[z]+=dep[x],dfs(z),siz[x]+=siz[z];
}
inline bool in(re int x,re int y){return dfn[y]>=dfn[x]&&dfn[y]<dfn[x]+siz[x];}
int main(){
	n=read(),m=read(),q=read();
	for(re int i=1;i<=n;++i)scanf("%s",s[i]+1);
	for(re int i=1;i<=n;++i)
		for(re int j=1;j<=m;++j){
			if(j>1&&s[i][j]!='L')Add(Pos(i,j),Pos(i,j-1));
			if(j<m&&s[i][j]!='R')Add(Pos(i,j),Pos(i,j+1));
			if(i>1&&s[i][j]!='U')Add(Pos(i,j),Pos(i-1,j));
			if(i<n&&s[i][j]!='D')Add(Pos(i,j),Pos(i+1,j));
		}
	for(re int i=1;i<=n*m;++i)if(!dfn[i])tj(i);
	for(re int i=1;i<=n*m;++i)
		for(auto z:A[i])
			if(bl[i]!=bl[z])
				Add1(bl[i],bl[z]);
	tim=0;
	printf("QQ%d\n",blk);
	for(re int i=blk;i;--i)if(!v[i])dfs(i);
	while(q--){
		re int X1=read(),Y1=read(),X2=read(),Y2=read(),p1=bl[Pos(X1,Y1)],p2=bl[Pos(X2,Y2)];
		if(!in(p1,p2))puts("0");
		else printf("%d\n",dep[p2]-dep[fa[p1]]);
	}
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 16ms
memory: 105244kb

input:

1 1 1
L
1 1 1 1

output:

QQ1
1

result:

wrong output format Expected integer, but "QQ1" found