QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#217029 | #3039. Cleaning | Crysfly | RE | 241ms | 301532kb | C++17 | 7.3kb | 2023-10-16 11:44:39 | 2023-10-16 11:44:40 |
Judging History
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 deg[maxn],out[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()
{
// freopen("maze.in","r",stdin);
// freopen("maze.out","w",stdout);
// read();
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;
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));
++deg[u],++deg[i],out[u]^=i,out[i]^=u;
}
}
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));
++deg[u],++deg[i],out[u]^=i,out[i]^=u;
}
}
// 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";
vi o;
for(int u:e[i]){
if(vis[u])continue;
if(deg[u]==0)o.pb(u);
if(deg[u]==1 && !vis[u]){
int x=u;
o.pb(x); vis[x]=1; x=out[x];
while(deg[x]!=1) o.pb(x),vis[x]=1,x=out[x]^(o[o.size()-2]);
o.pb(x); vis[x]=1;
}
}
e[i]=o;
For(j,0,(int)e[i].size()-1) pos[e[i][j]]=j;
}
for(auto [u,v]:E){
if(par[u]!=par[v]) exit(233);
if(abs(pos[u]-pos[v])!=1){
int x=par[u];
cout<<"par "<<x<<"\n";
for(int y:e[x]){
cout<<lx[y]<<" "<<ly[y]<<" "<<rx[y]<<" "<<ry[y]<<"\n";
}
exit(666);
}
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: 23ms
memory: 224688kb
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: 230840kb
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: 30ms
memory: 232976kb
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: 0
Accepted
time: 241ms
memory: 301532kb
input:
1000 1000 300000 RLLLURUDLURULUURLUDDLDDDRDDRUUDLLURRDDLLDRDLLRRRULUULLRRLRURRLLUUUUDUDDLUURDULDUDRRRUDLULRLDRDDUDULUUURLDUDDDUULLURUDRLRDLRULDUDUDDDLDUULRUUDLRLDURURLDDLLRRUURLULLRULLDURUDDDRUUUURUULRRRLLDLLUURUULDDLDRDLLDURLRDURLRLLDLUDLRULDUUDLDLULLULDDLUDLLLRURRRUUDLRLDLDLRDULRUDDURDRRLDRLRULDUL...
output:
0 0 0 0 0 0 245868 0 0 0 0 0 0 0 0 0 0 0 0 98541 0 0 0 89575 0 361225 0 262684 0 0 0 0 0 0 0 0 0 0 0 0 311462 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 361225 0 0 0 0 0 0 0 0 0 62676 0 0 136413 0 0 0 0 246844 0 178165 0 62676 361225 136413 0 0 361225 0 361225 0 0 0 199089 0 0 0 311462 0 0 262684 0 199...
result:
ok 300000 numbers
Test #5:
score: -100
Runtime Error
input:
1000 1000 300000 RRUDRRRRRDUULRUDLLULDRUDLDUDUDRUUUDURDDDRLURUURDURLDRDUUDUDLLUDDLRUDULUDDULDUULRRLUUDLLURLLRLDRLLDRDLUUDRDDUDRLLRDDDRURLRRDUDRRURRUDRRURRLLDULULRUDLLURDDULURDUULLUUUULLRURLLUURRUDLDUDRLLUDLDUDRLUUUUURLDRUDLRRLLLRRDLLDLRDUULDUDDULRURRDLRUDDRDLDLDDRLDRLRUDUURDURUURRDRRDLDLDDLRDRDLDDLL...