QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#359241 | #3039. Cleaning | Flamire | WA | 8ms | 70488kb | C++17 | 6.3kb | 2024-03-20 15:14:29 | 2024-03-20 15:14:30 |
Judging History
answer
#pragma gcc optimize(2,3,"Ofast")
#include <bits/stdc++.h>
#define id(i,j) (((i)-1)*m+(j))
#define N 1000011
#define TIME chrono::steady_clock::now().time_since_epoch().count()
using namespace std;
namespace IO
{
char Is[(1<<21)+10],Os[(1<<21)+10];
int Ipt,Opt;
char gc()
{
if(Ipt==1<<21)Ipt=0;
if(!Ipt){Is[fread(Is,1,1<<21,stdin)]=0;}
return Is[Ipt++];
}
void flush(){fwrite(Os,1,Opt,stdout);Opt=0;}
void pc(char x)
{
if(Opt==1<<21)flush();
Os[Opt++]=x;
}
int read()
{
int x=0;char ch=gc();while(ch<'0'||ch>'9')ch=gc();while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=gc();return x;
}
void write(int x){if(x<10)pc(x+'0');else write(x/10),pc(x%10+'0');}
char readc(){char ch=gc();while(ch<'A'||ch>'Z')ch=gc();return ch;}
}
using namespace IO;
int n,m,q,ans[N];char s[1011][1011];
struct edge{int v,next;edge(){}edge(int _v,int _next){v=_v;next=_next;}}e[N*3];int head[N],sz;
void init(){memset(head,-1,sizeof(head));sz=0;}void insert(int u,int v){e[++sz]=edge(v,head[u]);head[u]=sz;}
int dfn[N],low[N],stk[N],scc[N],nscc=0,w[N],clk;bool vis[N];
void tarjan(int u)
{
dfn[u]=low[u]=++clk;vis[u]=1;stk[++stk[0]]=u;
for(int i=head[u];~i;i=e[i].next)
{
if(!dfn[e[i].v])tarjan(e[i].v),low[u]=min(low[u],low[e[i].v]);
else if(vis[e[i].v])low[u]=min(low[u],dfn[e[i].v]);
}
if(dfn[u]==low[u])
{
scc[u]=nscc;++w[nscc];vis[u]=0;
while(stk[stk[0]]!=u)scc[stk[stk[0]]]=nscc,++w[nscc],vis[stk[stk[0]--]]=0;
--stk[0];++nscc;
}
}
long long SS,CNT,S1,CNT1;
namespace sol_1
{
int id[N],rk[N],in[N],nid[N],gg[N][4],tg[N][4];bool vis[N],ok[N];vector<int> G[N];
int Q[N],ql,qr;
struct kueri{int S,T,id;};vector<kueri> vq[N];
void bfs(int s)
{
ql=qr=0;Q[qr++]=s;vis[s]=1;id[++id[0]]=s;rk[s]=id[0];vis[nscc+1]=1;
while(ql^qr)
{
int p=Q[ql++];//++CNT;
// if(G[p].size()>0)
// {
++in[gg[p][0]];
if(!vis[gg[p][0]])
{
vis[gg[p][0]]=1;
id[++id[0]]=gg[p][0];
Q[qr++]=gg[p][0];
}
// if(G[p].size()>1)
// {
++in[gg[p][1]];
if(!vis[gg[p][1]])
{
vis[gg[p][1]]=1;
id[++id[0]]=gg[p][1];
Q[qr++]=gg[p][1];
}
// if(G[p].size()>2)
// {
++in[gg[p][2]];
if(!vis[gg[p][2]])
{
vis[gg[p][2]]=1;
id[++id[0]]=gg[p][2];
Q[qr++]=gg[p][2];
}
// if(G[p].size()>3)
// {
++in[gg[p][3]];
if(!vis[gg[p][3]])
{
vis[gg[p][3]]=1;
id[++id[0]]=gg[p][3];
Q[qr++]=gg[p][3];
}
// }
// }
// }
// }
// for(int v:G[p])if(!vis[v])
// {
// vis[v]=1;
// id[++id[0]]=v;
// Q[qr++]=v;
// }
}
}
void Solve(int x)
{//printf("Solve(%d)\n",x);
// SS=TIME;
bfs(x);//fprintf(stderr,"CNT:%d\n",CNT);CNT=0;
// for(int i=1;i<=id[0];++i)
// {
// // for(int v:G[id[i]])if(vis[v])++in[v];
// if(G[id[i]].size()>0)
// {
// if(vis[gg[id[i]][0]])++in[gg[id[i]][0]];
// if(G[id[i]].size()>1)
// {
// if(vis[gg[id[i]][1]])++in[gg[id[i]][1]];
// if(G[id[i]].size()>2)
// {
// if(vis[gg[id[i]][2]])++in[gg[id[i]][2]];
// if(G[id[i]].size()>3)
// {
// if(vis[gg[id[i]][3]])++in[gg[id[i]][3]];
// }
// }
// }
// }
// }
// CNT1+=TIME-SS;
ql=qr=0;
for(int i=1;i<=id[0];++i)if(!in[id[i]])Q[qr++]=id[i];vis[nscc+1]=0;
while(ql!=qr)
{
int p=Q[ql];
nid[++nid[0]]=p;++ql;
// if(G[p].size()>0)
// {
if(vis[gg[p][0]]&&!--in[gg[p][0]])Q[qr++]=gg[p][0];
// if(G[p].size()>1)
// {
if(vis[gg[p][1]]&&!--in[gg[p][1]])Q[qr++]=gg[p][1];
// if(G[p].size()>2)
// {
if(vis[gg[p][2]]&&!--in[gg[p][2]])Q[qr++]=gg[p][2];
// if(G[p].size()>3)
// {
if(vis[gg[p][3]]&&!--in[gg[p][3]])Q[qr++]=gg[p][3];
// }
// }
// }
// }
// for(int v:G[p])if(vis[v]&&!--in[v])Q[qr++]=v;
}
for(int i=1;i<=id[0];++i)id[i]=nid[i];
nid[0]=0;
for(int i=1;i<=id[0];++i)rk[id[i]]=i;
for(int i=1;i<=id[0];++i)tg[i][0]=rk[gg[id[i]][0]],tg[i][1]=rk[gg[id[i]][1]],tg[i][2]=rk[gg[id[i]][2]],tg[i][3]=rk[gg[id[i]][3]];
// printf("id:");for(int i=1;i<=id[0];++i)printf("%d ",id[i]);putchar(10);
// SS=TIME;
for(kueri k:vq[x])
{
if(!vis[k.T])continue;
ok[rk[k.T]]=1;
for(int i=rk[k.T]-1;i;--i)
{
ok[i]=id[i]==k.T;++CNT;
// if(G[id[i]].size()>0)
// {
ok[i]|=ok[tg[i][0]];
// if(G[id[i]].size()>1)
// {
ok[i]|=ok[tg[i][1]];
// if(G[id[i]].size()>2)
// {
ok[i]|=ok[tg[i][2]];
// if(G[id[i]].size()>3)
// {
ok[i]|=ok[tg[i][3]];
// }
// }
// }
// }
// for(int v:G[id[i]])if(rk[v])ok[i]|=ok[rk[v]];
}
for(int i=1;i<=rk[k.T];++i)ans[k.id]+=w[id[i]]*ok[i];
for(int i=1;i<=rk[k.T];++i)ok[i]=0;
}//printf("id0:%d\n",id[0]);
// CNT1+=TIME-SS;
for(int i=1;i<=id[0];++i)rk[id[i]]=vis[id[i]]=0;id[0]=0;
}
void main()
{
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(!dfn[id(i,j)])tarjan(id(i,j));
for(int i=1;i<=n*m;++i)for(int j=head[i];~j;j=e[j].next)if(scc[i]!=scc[e[j].v])G[scc[i]].push_back(scc[e[j].v]);
// printf("scc:\n");for(int i=1;i<=n*m;++i){printf("%d ",scc[i]);if(i%m==0)putchar(10);}
for(int i=0;i<nscc;++i)sort(G[i].begin(),G[i].end()),G[i].resize(unique(G[i].begin(),G[i].end())-G[i].begin());
for(int i=0;i<nscc;++i){for(int j=0;j<G[i].size();++j)gg[i][j]=G[i][j];for(int j=G[i].size();j<4;++j)gg[i][j]=nscc+1;}
// for(int i=0;i<nscc;++i){for(int v:G[i])printf("%d ",v);putchar(10);}
for(int _=1;_<=q;++_)
{
int a,b,c,d,x,y;
a=read();b=read();c=read();d=read();
kueri k;k.S=scc[id(a,b)];k.T=scc[id(c,d)];k.id=_;
vq[k.S].push_back(k);
}
for(int i=0;i<nscc;++i)if(vq[i].size())Solve(i);
for(int i=1;i<=q;++i)
{
if(!ans[i])pc('-'),pc('1'),pc(10);
else write(ans[i]),pc(10);
}
flush();
}
}
int main()
{
n=read();m=read();q=read();init();
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)s[i][j]=readc();
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(i>1&&s[i][j]!='U')insert(id(i,j),id(i-1,j));
if(i<n&&s[i][j]!='D')insert(id(i,j),id(i+1,j));
if(j>1&&s[i][j]!='L')insert(id(i,j),id(i,j-1));
if(j<m&&s[i][j]!='R')insert(id(i,j),id(i,j+1));
}
}
sol_1::main();//printf("CNT:%lld CNT1:%.9lfs\n",CNT,CNT1/1e9);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 70488kb
input:
1 1 1 L 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 8ms
memory: 69804kb
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:
-1 14 20 14 5
result:
wrong answer 1st numbers differ - expected: '0', found: '-1'