QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#359222 | #3039. Cleaning | Harry27182 | RE | 0ms | 38708kb | C++14 | 2.0kb | 2024-03-20 14:57:19 | 2024-03-20 14:57:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct edge{int v,nxt;}e[4000005];
int cnt,h[1000005],dfn[1000005],low[1000005],vis[1000005],tot,n,m,Q,sx,sy,tx,ty;
int num,col[1000005],siz[1000005],in[1000005];
stack<int>st;char s[1005][1005];vector<int>g[1000005];bitset<10005>bs[10005];
void add(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
int id(int x,int y){return (x-1)*m+y;}
void tarjan(int u)
{
dfn[u]=low[u]=++tot;st.push(u);vis[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
num++;
while(!st.empty())
{
int x=st.top();st.pop();
col[x]=num;siz[num]++;vis[x]=0;
if(x==u)break;
}
}
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>Q;
for(int i=1;i<=n;i++)
{
cin>>(s[i]+1);
for(int j=1;j<=m;j++)
{
if(s[i][j]!='L'&&j-1>=1)add(id(i,j),id(i,j-1));
if(s[i][j]!='R'&&j+1<=m)add(id(i,j),id(i,j+1));
if(s[i][j]!='U'&&i-1>=1)add(id(i,j),id(i-1,j));
if(s[i][j]!='D'&&i+1<=n)add(id(i,j),id(i+1,j));
}
}
for(int i=1;i<=n*m;i++)if(!dfn[i])tarjan(i);
for(int u=1;u<=n*m;u++)
{
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(col[u]!=col[v])g[col[u]].emplace_back(col[v]);
}
}
for(int i=1;i<=num;i++)
{
sort(g[i].begin(),g[i].end());
vector<int>now;
for(int j=0;j<g[i].size();j++)if(j==0||g[i][j]!=g[i][j-1])now.emplace_back(g[i][j]);
swap(g[i],now);
for(int j=0;j<g[i].size();j++)in[g[i][j]]++;
}
queue<int>q;
for(int i=1;i<=num;i++)if(!in[i])q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
bs[u][u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
bs[v]|=bs[u];in[v]--;
if(!in[v])q.push(v);
}
}
assert(num<=n&&num<=m);
while(Q--)
{
cin>>sx>>sy>>tx>>ty;
int x=col[id(sx,sy)],y=col[id(tx,ty)];
if(!bs[y][x]){cout<<0<<'\n';continue;}
int ans=0;
for(int i=1;i<=num;i++)if(bs[y][i]&&bs[i][x])ans+=siz[i];
cout<<ans<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 38708kb
input:
1 1 1 L 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Runtime Error
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