QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359241#3039. CleaningFlamireWA 8ms70488kbC++176.3kb2024-03-20 15:14:292024-03-20 15:14:30

Judging History

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

  • [2024-03-20 15:14:30]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:70488kb
  • [2024-03-20 15:14:29]
  • 提交

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;
}

詳細信息

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'