QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#65970 | #3039. Cleaning | gyh20 | WA | 16ms | 105244kb | C++14 | 1.9kb | 2022-12-04 19:59:25 | 2022-12-04 19:59:27 |
Judging History
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