QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#359232#3039. CleaningHarry27182RE 4ms29060kbC++142.0kb2024-03-20 15:01:472024-03-20 15:01:47

Judging History

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

  • [2024-03-20 15:01:47]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:29060kb
  • [2024-03-20 15:01:47]
  • 提交

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<=4000);
	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: 4ms
memory: 28748kb

input:

1 1 1
L
1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 4ms
memory: 29060kb

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: 3ms
memory: 28228kb

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
Runtime Error

input:

1000 1000 300000
RLLLURUDLURULUURLUDDLDDDRDDRUUDLLURRDDLLDRDLLRRRULUULLRRLRURRLLUUUUDUDDLUURDULDUDRRRUDLULRLDRDDUDULUUURLDUDDDUULLURUDRLRDLRULDUDUDDDLDUULRUUDLRLDURURLDDLLRRUURLULLRULLDURUDDDRUUUURUULRRRLLDLLUURUULDDLDRDLLDURLRDURLRLLDLUDLRULDUUDLDLULLULDDLUDLLLRURRRUUDLRLDLDLRDULRUDDURDRRLDRLRULDUL...

output:


result: