QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#217022#3039. CleaningCrysflyRE 28ms229276kbC++176.8kb2023-10-16 11:26:122023-10-16 11:26:12

Judging History

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

  • [2023-10-16 11:26:12]
  • 评测
  • 测评结果:RE
  • 用时:28ms
  • 内存:229276kb
  • [2023-10-16 11:26:12]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int __int128
//#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 2000005
#define inf 0x3f3f3f3f

int n,m,Q,cnt;
int a[1005][1005];
vi g[maxn];
vi g2[maxn];
char str[maxn];

// L D R U.
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char opt[4]={'R','D','L','U'};

int getx(char c){
	For(i,0,3) if(opt[i]==c) return i;
	assert(0);
}
int P(int i,int j){
	return (i-1)*m+j;
}
int X(int i){
	return (i-1)/m+1;
}
int Y(int i){
	return (i-1)%m+1;
}
int px[maxn],py[maxn],op[maxn];

int dfn[maxn],low[maxn],idx,scc,st[maxn],tp,bel[maxn];
vi p[maxn];
int lx[maxn],rx[maxn],ly[maxn],ry[maxn];

void tar(int u){
	dfn[u]=low[u]=++idx;
	st[++tp]=u;
	for(int v:g[u]){
		if(!dfn[v])tar(v),low[u]=min(low[u],low[v]);
		else if(!bel[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]!=low[u])return;
	int v; ++scc; do{
		v=st[tp--];
		bel[v]=scc;
		p[scc].pb(v);
	} while(u!=v);
}

bool vis[maxn];
int par[maxn];

int dsu[maxn];
int gf(int x){
	while(x!=dsu[x])x=dsu[x]=dsu[dsu[x]];
	return x;
}

int rt;
vi e[maxn];

int pos[maxn],eto[maxn];

int fa[maxn][21],dep[maxn],sum[maxn],val[maxn],L[maxn],R[maxn];

int Sum(int l,int r){
	return sum[r]-sum[l]+p[l].size();
}
void dfs(int u){
//	cout<<"dfs u: "<<u<<" "<<par[u]<<"\n";
	dep[u]=dep[par[u]]+1;
	fa[u][0]=par[u];
	For(i,1,20)fa[u][i]=fa[fa[u][i-1]][i-1];
	int sz=e[u].size();
	
	int now=0;
	for(int v:e[u])now+=p[v].size(),sum[v]=now;
	int lst=-1;
	for(int v:e[u]){
		if(lst==-1 || eto[lst]!=-1) L[v]=v;
		else L[v]=L[lst];
		lst=v;
	}
	lst=-1;
	Rep(i,sz-1,0){
		int v=e[u][i];
		if(eto[v]!=1) R[v]=v;
		else assert(lst!=-1),R[v]=R[lst];
		lst=v;
	}
	for(int v:e[u])val[v]=Sum(L[v],R[v]);
	for(int v:e[u])val[v]+=val[u],dfs(v);
}

int ask(int u,int v){
//	cout<<"ask "<<u<<" "<<v<<"\n";
	if(dep[u]<dep[v])return 0;
	int res=val[u];
	Rep(i,20,0)
		if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
	res-=val[u];
	if(fa[u][0]!=fa[v][0])return 0;
//	cout<<"u: "<<u<<" "<<L[u]<<" "<<R[u]<<"\n";
//	cout<<"fa "<<fa[u][0]<<" "<<fa[v][0]<<"\n";
	if(pos[u]<pos[v]){
		if(pos[R[u]]>=pos[v])return Sum(u,v)+res;
		return 0;
	}
	else{
		if(pos[L[u]]<=pos[v])return Sum(v,u)+res;
		return 0;
	}
}

signed main()
{
	n=read(),m=read(),Q=read();
	For(i,1,n){
		scanf("%s",str);
		For(j,1,m)a[i][j]=getx(str[j-1]);
	}
	
	For(i,1,n)
		For(j,1,m){
			For(d,0,3)
				if(d!=a[i][j]){
					int ii=i+dx[d],jj=j+dy[d];
					if(ii>0&&jj>0&&ii<=n&&jj<=m)
						g[P(i,j)].pb(P(ii,jj));
				}
		}
	For(i,1,n*m)if(!dfn[i])tar(i);
	
//	For(i,1,n)
//		For(j,1,m) cout<<bel[P(i,j)]<<" \n"[j==m];
	
	For(i,1,n*m*2+1) dsu[i]=i;
	For(u,1,n*m)
		for(int v:g[u]) if(bel[u]!=bel[v]) g2[bel[v]].pb(bel[u]);
	cnt=scc;
	vector<pii>E;
	For(i,1,scc){
		px[i]=X(p[i][0]);
		py[i]=Y(p[i][0]);
	}
	Rep(i,scc,1){
	//	cout<<"work "<<i<<"\n";
		sort(g2[i].begin(),g2[i].end());
		g2[i].erase(unique(g2[i].begin(),g2[i].end()),g2[i].end());
		lx[i]=ly[i]=inf,rx[i]=ry[i]=0;
		for(auto u:p[i]){
			int x=(u-1)/m+1;
			int y=(u-1)%m+1;
			lx[i]=min(lx[i],x);
			rx[i]=max(rx[i],x);
			ly[i]=min(ly[i],y);
			ry[i]=max(ry[i],y);
		}
		for(int j:g2[i]){
			// j->i
			j=gf(j);
			if(j==i)continue;
			if(lx[j]>=lx[i] && rx[j]<=rx[i] && ly[j]>=ly[i] && ry[j]<=ry[i]){
			//	cout<<"i: "<<lx[i]<<" "<<ly[i]<<" "<<rx[i]<<" "<<ry[i]<<"\n";
			//	cout<<"j: "<<lx[j]<<" "<<ly[j]<<" "<<rx[j]<<" "<<ry[j]<<"\n";
				par[j]=i;
				vis[j]=1;
				dsu[j]=i;
			//	cout<<"merge "<<j<<" "<<i<<"\n";
			}
		}
		for(int x:{lx[i]-1,rx[i]+1}){
			if(x<=0||x>n)continue;
			if(bel[P(x,ly[i])]<i) continue;
			int u=gf(bel[P(x,ly[i])]),lst=u;
			bool hav=0;
			vi o; o.pb(u);
			For(y,ly[i],ry[i]){
				int v=gf(bel[P(x,y)]);
				if(x==lx[i]-1 && x+dx[a[x][y]]!=lx[i]) hav=1;
				if(x==rx[i]+1 && x+dx[a[x][y]]!=rx[i]) hav=1;
				if(v!=lst) o.pb(v),lst=v;
			}
			if(o.size()>1){
			//	puts("qaq");
			//	for(int v:o)cout<<v<<" "; puts("");
				px[cnt+1]=px[u];
				py[cnt+1]=py[u];
				op[cnt+1]=1;//0.
				u=++cnt;
//				cout<<"Create New: "<<cnt<<"\n";
//				for(int v:o)cout<<v<<" ";puts("");
				lx[u]=ly[u]=inf;
				// create new.
				for(int v:o){
					par[v]=dsu[v]=u;
					lx[u]=min(lx[u],lx[v]);
					ly[u]=min(ly[u],ly[v]);
					rx[u]=max(rx[u],rx[v]);
					ry[u]=max(ry[u],ry[v]);
				}
			}
			if(hav){
				// adde (u,i).
			//	cout<<"add "<<u<<" "<<i<<"\n";
				E.pb(mkp(u,i));
			}
		}
		for(int y:{ly[i]-1,ry[i]+1}){
			if(y<=0||y>m)continue;
			if(bel[P(lx[i],y)]<i)continue;
			int u=gf(bel[P(lx[i],y)]),lst=u;
			bool hav=0;
			vi o; o.pb(u);
			For(x,lx[i],rx[i]){
				int v=gf(bel[P(x,y)]);
				if(y==ly[i]-1 && y+dy[a[x][y]]!=ly[i]) hav=1;
				if(y==ry[i]+1 && y+dy[a[x][y]]!=ry[i]) hav=1;
				if(v!=lst) o.pb(v),lst=v;
			}
			if(o.size()>1){
			//	puts("qaq");
			//	for(int v:o)cout<<v<<" "; puts("");
				px[cnt+1]=px[u];
				py[cnt+1]=py[u];
				op[cnt+1]=2;//y.
				u=++cnt;
//				cout<<"Create New: "<<cnt<<"\n";
//				for(int v:o)cout<<v<<" ";puts("");
				lx[u]=ly[u]=inf;
				// create new.
				for(int v:o){
					par[v]=dsu[v]=u;
					lx[u]=min(lx[u],lx[v]);
					ly[u]=min(ly[u],ly[v]);
					rx[u]=max(rx[u],rx[v]);
					ry[u]=max(ry[u],ry[v]);
				}
			}
			if(hav){
				// adde (u,i).
				E.pb(mkp(u,i));
			}
		}
	//	cout<<"cnt "<<cnt<<"\n";
	}
	
//	cout<<"edges:\n";
//	for(auto [u,v]:E) cout<<u<<" "<<v<<"\n";
//	cout<<"L&&R:\n";
	//For(i,1,cnt){
//		cout<<lx[i]<<" "<<ly[i]<<" "<<rx[i]<<" "<<ry[i]<<"\n";
//	}
	
	rt=++cnt;
	For(i,1,cnt-1){
		if(gf(i)==i) par[i]=dsu[i]=rt;
		e[par[i]].pb(i);
	}
//	For(i,1,cnt) cout<<par[i]<<" ";cout<<"  par\n";
	For(i,1,cnt){
		sort(e[i].begin(),e[i].end(),[&](int u,int v){
			return mkp(lx[u],ly[u])<mkp(lx[v],ly[v]);
		});
	//	cout<<"child:\n";
	//	for(int v:e[i]) cout<<v<<" "; cout<<"\n";
		For(j,0,(int)e[i].size()-1) pos[e[i][j]]=j;
	}
	for(auto [u,v]:E){
		assert(par[u]==par[v]);
		assert(abs(pos[u]-pos[v])==1);
		if(pos[u]<pos[v]) eto[u]=1;
		else eto[v]=-1;
	}
	dfs(rt);
	For(_,1,Q){
		int a=read(),b=read(),c=read(),d=read();
		int u=bel[P(a,b)],v=bel[P(c,d)];
		cout<<ask(u,v)<<"\n";
	}
	return 0;
}
/*
4 2
18 14 4
*/

详细

Test #1:

score: 100
Accepted
time: 20ms
memory: 224908kb

input:

1 1 1
L
1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 28ms
memory: 229276kb

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: 20ms
memory: 228952kb

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: