QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #386152 | #3039. Cleaning | fantis | WA | 103ms | 209484kb | C++14 | 7.3kb | 2024-04-11 13:03:33 | 2024-04-11 13:03:34 |
Judging History
answer
#include<bits/stdc++.h>//0xnnb
using namespace std;
typedef long long ll;
typedef double db;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=1005,NN=2000005,M=4000005;
int n,m,q,ee,vex[NN],tim,dfn[NN],low[NN];
int stk[NN],top,col[NN],cnt,sum[NN];
int f[NN],fa[NN],nxtl[NN],nxtr[NN],rt;
int pos[NN],maxl[NN],maxr[NN];
bool gol[NN],gor[NN];
int xl[NN],xr[NN],yl[NN],yr[NN],fa2[NN][25];
int sum2[NN],sum3[NN],dep[NN];
bool instk[NN],vis[NN];
char a[N][N];
vector<int>p[NN],son[NN],e2[NN];
struct Node{
int u,v,next;
}e[M];
int id(int x,int y){
return (x-1)*m+y;
}
int getx(int u){
return (u-1)/m+1;
}
int gety(int u){
return (u-1)%m+1;
}
void add(int u,int v){
e[++ee].u=u,e[ee].v=v;
e[ee].next=vex[u],vex[u]=ee;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
stk[++top]=u;
instk[u]=1;
for(int i=vex[u];i;i=e[i].next){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instk[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
cnt++;
while(1){
int x=stk[top--];
col[x]=cnt;
instk[x]=0;
p[cnt].push_back(x);
sum[cnt]++;
if(x==u)break;
}
}
}
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
void addnode(int x){
vis[x]=1;
if(nxtl[x]&&(!vis[nxtl[x]]))addnode(nxtl[x]);
stk[++top]=x;
if(nxtr[x]&&(!vis[nxtr[x]]))addnode(nxtr[x]);
}
int getsum(int x,int y){
return sum2[y]-sum2[nxtl[x]];
}
void dfs(int u){
sum3[u]+=getsum(maxl[u],maxr[u]);
dep[u]=dep[fa[u]]+1;
fa2[u][0]=fa[u];
for(int i=1;i<=20;i++){
fa2[u][i]=fa2[fa2[u][i-1]][i-1];
}
int tmp=son[u].size();
for(int i=0;i<tmp;i++){
int v=son[u][i];
sum3[v]+=sum3[u];
dfs(v);
}
}
int solve(int x,int y){
x=col[x],y=col[y];
if(dep[x]<dep[y])return 0;
int ans=sum3[x];
for(int i=20;i>=0;i--){
if(dep[fa2[x][i]]<dep[y])continue;
x=fa2[x][i];
}
ans-=sum3[x];
if(x==y)return ans+sum[x];
if(fa[x]!=fa[y])return 0;
if(pos[x]<=pos[y]){
if(q>=10000){
int tmp=x;
cout<<x<<"->"<<y<<endl;
while(1){
cout<<tmp<<":"<<pos[tmp]<<" "<<gol[tmp]<<" "<<gor[tmp]<<" "<<xl[tmp]<<" "<<xr[tmp]<<" "<<yl[tmp]<<" "<<yr[tmp]<<endl;
if(tmp==y)break;
tmp=nxtr[tmp];
}
cout<<"fa"<<fa[x]<<" "<<xl[fa[x]]<<" "<<xr[fa[x]]<<endl;
cout<<ans<<" "<<getsum(x,y)<<endl;
return ans+getsum(x,y);
}
if(pos[maxr[x]]<pos[y])return 0;
return ans+getsum(x,y);
}
else{
if(pos[maxl[x]]>pos[y])return 0;
return ans+getsum(y,x);
}
}
int main(){
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!='U'&&i>1)add(id(i,j),id(i-1,j));
if(a[i][j]!='D'&&i<n)add(id(i,j),id(i+1,j));
if(a[i][j]!='L'&&j>1)add(id(i,j),id(i,j-1));
if(a[i][j]!='R'&&j<m)add(id(i,j),id(i,j+1));
}
}
for(int i=1;i<=n*m;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=ee;i++){
int u=e[i].u,v=e[i].v;
if(col[u]!=col[v]){
e2[col[v]].push_back(col[u]);
}
}
for(int i=1;i<=cnt;i++){
f[i]=i;
}
for(int i=cnt;i>=1;i--){
xl[i]=yl[i]=1000;
for(int j=0;j<sum[i];j++){
int u=p[i][j];
int x=getx(u),y=gety(u);
xl[i]=min(xl[i],x),xr[i]=max(xr[i],x);
yl[i]=min(yl[i],y),yr[i]=max(yr[i],y);
}
int tmp=e2[i].size();
for(int j=0;j<tmp;j++){
int u=e2[i][j];
int uu=p[u][0];
u=find(u);
if(u==i)continue;
int x=getx(uu),y=gety(uu);
if(x>=xl[i]&&x<=xr[i]&&y>=yl[i]&&y<=yr[i]){
f[u]=fa[u]=i;
}
}
//L
if(yl[i]!=1){
bool flag=0;
for(int j=xl[i];j<=xr[i];j++){
int u=id(j,yl[i]-1);
u=col[u];
if(u<i)continue;
u=find(u);
if(instk[u])continue;
stk[++top]=u;
instk[u]=1;
if(a[j][yl[i]-1]!='R')flag=1;
}
if(top>1){
cnt++;
f[cnt]=cnt;
xl[cnt]=yl[cnt]=1000;
for(int j=1;j<=top;j++){
int u=stk[j];
xl[cnt]=min(xl[cnt],xl[u]),xr[cnt]=max(xr[cnt],xr[u]);
yl[cnt]=min(yl[cnt],yl[u]),yr[cnt]=max(yr[cnt],yr[u]);
f[u]=fa[u]=cnt;
}
nxtl[i]=cnt;
nxtr[cnt]=i;
}
else if(top==1)nxtl[i]=stk[1],nxtr[stk[1]]=i;
if(flag)gor[nxtl[i]]=1;
while(top)instk[stk[top--]]=0;
}
//R
if(yr[i]!=m){
bool flag=0;
for(int j=xl[i];j<=xr[i];j++){
int u=id(j,yr[i]+1);
u=col[u];
if(u<i)continue;
u=find(u);
if(instk[u])continue;
stk[++top]=u;
instk[u]=1;
if(a[j][yr[i]+1]!='L')flag=1;
}
if(top>1){
cnt++;
f[cnt]=cnt;
xl[cnt]=yl[cnt]=1000;
for(int j=1;j<=top;j++){
int u=stk[j];
xl[cnt]=min(xl[cnt],xl[u]),xr[cnt]=max(xr[cnt],xr[u]);
yl[cnt]=min(yl[cnt],yl[u]),yr[cnt]=max(yr[cnt],yr[u]);
f[u]=fa[u]=cnt;
}
nxtr[i]=cnt,nxtl[cnt]=i;
}
else if(top==1)nxtr[i]=stk[1],nxtl[stk[1]]=i;
if(flag)gol[nxtr[i]]=1;
while(top)instk[stk[top--]]=0;
}
//U
if(xl[i]!=1){
bool flag=0;
for(int j=yl[i];j<=yr[i];j++){
int u=id(xl[i]-1,j);
u=col[u];
if(u<i)continue;
u=find(u);
if(instk[u])continue;
stk[++top]=u;
instk[u]=1;
if(a[xl[i]-1][j]!='D')flag=1;
}
if(top>1){
cnt++;
f[cnt]=cnt;
xl[cnt]=yl[cnt]=1000;
for(int j=1;j<=top;j++){
int u=stk[j];
xl[cnt]=min(xl[cnt],xl[u]),xr[cnt]=max(xr[cnt],xr[u]);
yl[cnt]=min(yl[cnt],yl[u]),yr[cnt]=max(yr[cnt],yr[u]);
f[u]=fa[u]=cnt;
}
nxtl[i]=cnt,nxtr[cnt]=i;
}
else if(top==1)nxtl[i]=stk[1],nxtr[stk[1]]=i;
if(flag)gor[nxtl[i]]=1;
while(top)instk[stk[top--]]=0;
}
//D
if(xr[i]!=n){
bool flag=0;
for(int j=yl[i];j<=yr[i];j++){
int u=id(xr[i]+1,j);
u=col[u];
if(u<i)continue;
u=find(u);
if(instk[u])continue;
stk[++top]=u;
instk[u]=1;
if(a[xr[i]+1][j]!='U')flag=1;
}
if(top>1){
cnt++;
f[cnt]=cnt;
xl[cnt]=yl[cnt]=1000;
for(int j=1;j<=top;j++){
int u=stk[j];
xl[cnt]=min(xl[cnt],xl[u]),xr[cnt]=max(xr[cnt],xr[u]);
yl[cnt]=min(yl[cnt],yl[u]),yr[cnt]=max(yr[cnt],yr[u]);
f[u]=fa[u]=cnt;
}
nxtr[i]=cnt,nxtl[cnt]=i;
}
else if(top==1)nxtr[i]=stk[1],nxtl[stk[1]]=i;
if(flag)gol[nxtr[i]]=1;
while(top)instk[stk[top--]]=0;
}
}
for(int i=1;i<=cnt;i++){
if(!fa[i]){
stk[++top]=i;
}
}
if(top==1)rt=stk[1];
else{
rt=++cnt;
for(int i=1;i<=top;i++){
fa[stk[i]]=rt;
}
}
top=0;
for(int i=1;i<=cnt;i++){
if(fa[i]){
son[fa[i]].push_back(i);
}
}
for(int i=1;i<=cnt;i++){
int tmp=son[i].size();
for(int j=0;j<tmp;j++){
int u=son[i][j];
if(!vis[u])addnode(u);
}
for(int i=1;i<=top;i++){
pos[stk[i]]=i;
sum2[stk[i]]=sum2[stk[i-1]]+sum[stk[i]];
}
for(int i=1;i<=top;i++){
if(!gol[stk[i]]){
maxl[stk[i]]=stk[i];
}
else{
maxl[stk[i]]=maxl[stk[i-1]];
}
}
for(int i=top;i>=1;i--){
if(!gor[stk[i]]){
maxr[stk[i]]=stk[i];
}
else{
maxr[stk[i]]=maxr[stk[i+1]];
}
}
top=0;
}
pos[rt]=1;
maxl[rt]=maxr[rt]=rt;
dfs(rt);
for(int qq=1;qq<=q;qq++){
int x1=read(),y1=read(),x2=read(),y2=read();
if(q>=10000&&qq!=248)continue;
printf("%d\n",solve(id(x1,y1),id(x2,y2)));
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 12ms
memory: 144644kb
input:
1 1 1 L 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 23ms
memory: 144540kb
input:
5 5 5 DDDDD RDDDL RRDLL RUUUL UUUUU 1 1 5 5 2 2 5 5 3 3 5 5 4 4 5 5 5 5 5 5
output:
0 14 20 14 5
result:
ok 5 number(s): "0 14 20 14 5"
Test #3:
score: 0
Accepted
time: 11ms
memory: 144580kb
input:
10 10 15 DDDDDDDDLU LRDLRRDLLU DDDLRRDLLD RRLLDUULLD RRLLURLRLD RRLLRRLDLU RRLLURLULU UULLURLULU DRULUUUULD RRRLDRLRLD 7 4 2 5 4 7 6 8 6 6 5 6 5 6 9 6 9 10 5 5 2 5 4 3 7 9 4 4 10 9 1 5 9 9 8 9 1 4 7 8 10 2 5 10 7 9 1 3 7 6 7 7 5 6 10 2 2 6 4 2
output:
41 41 41 41 0 0 0 0 20 0 88 0 41 0 0
result:
ok 15 numbers
Test #4:
score: -100
Wrong Answer
time: 103ms
memory: 209484kb
input:
1000 1000 300000 RLLLURUDLURULUURLUDDLDDDRDDRUUDLLURRDDLLDRDLLRRRULUULLRRLRURRLLUUUUDUDDLUURDULDUDRRRUDLULRLDRDDUDULUUURLDUDDDUULLURUDRLRDLRULDUDUDDDLDUULRUUDLRLDURURLDDLLRRUURLULLRULLDURUDDDRUUUURUULRRRLLDLLUURUULDDLDRDLLDURLRDURLRLLDLUDLRULDUUDLDLULLULDDLUDLLLRURRRUUDLRLDLDLRDULRUDDURDRRLDRLRULDUL...
output:
1340->1338 1340:7 1 1 304 567 1 1000 1339:8 0 0 568 574 1 1000 1338:9 0 0 575 585 1 1000 fa4440 0 0 0 280593 280593
result:
wrong output format Expected integer, but "1340->1338" found