QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#164254 | #6615. Cross the Maze | LFCode | WA | 4ms | 5956kb | C++14 | 3.7kb | 2023-09-04 20:57:10 | 2023-09-04 20:57:10 |
Judging History
answer
#include<cstdio>
#include<cstdlib>
#define lg(x) (31-__builtin_clz(x))
#define llg(x) (63-__builtin_clzll(x))
const int N=114,P=100086,MOD=998244353,INF=1e9+7;
int n,a,b,qh,qt,s,t,tot,ax,ay;
int px[N],py[N],qx[N],qy[N],d[P],h[P],fir[P],q[P];
int xx[4]={-1,0,1,0},
yy[4]={0,-1,0,1};
char ansl[N*3];
struct edge{int v,w,nxt;}e[5000086];
int Abs(int x){return x<0?-x:x;}
int lowbit(int x){return x&(-x);}
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int Swap(int &a,int &b){a^=b^=a^=b;return true;}
int Add(int &a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int vAdd(int a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int Sub(int &a,int b){return(a-=b)<0?a+=MOD:a;}
int vSub(int a,int b){return(a-=b)<0?a+=MOD:a;}
int Mul(int a,int b){return 1ll*a*b%MOD;}
int qpow(int a,int b){
int ret=1;
while(b){if(b&1)ret=Mul(ret,a);a=Mul(a,a);b>>=1;}
return ret;
}
int read(){
char ch=getchar();int nn=0,ssss=1;
while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
bool add(int u,int v,int w){e[++tot].v=v;e[tot].w=w;e[tot].nxt=h[u];h[u]=tot;return true;}
bool otm(int x,int y){return x<1||x>a||y<1||y>b;}
int pos(int x,int y,int t,int flr){return (t*a*b+b*(x-1)+y)*2-flr;}
bool bfs(){
for(int i=0;i<=t;i++)fir[i]=d[i]=0;
d[q[qh=qt=1]=s]=1;fir[s]=h[s];
while(qh<=qt){
int np=q[qh++];
for(int i=h[np];i;i=e[i].nxt){
if(e[i].w==0||d[e[i].v])continue;
d[e[i].v]=d[np]+1;
fir[e[i].v]=h[e[i].v];
q[++qt]=e[i].v;
if(e[i].v==t){
while(0);
return true;
}
}
}
return false;
}
int dfs(int np,int flw){
if(np==t)return flw;int rst=flw;
for(int i=fir[np];i&&rst;i=e[i].nxt){
fir[np]=i;
if(e[i].w==0||d[e[i].v]!=d[np]+1)continue;
int k=dfs(e[i].v,Min(rst,e[i].w));
if(!k)d[e[i].v]=0;
e[i].w-=k;e[i^1].w+=k;rst-=k;
}
return flw-rst;
}
int dinic(){
int delta=0,ans=0;
while(bfs())while(delta=dfs(s,INF))ans+=delta;
return ans;
}
bool solve(int tme){
s=0;t=(tme+1)*a*b*2+1;tot=1;
for(int i=s;i<=t;i++)h[i]=0;
for(int i=0;i<=tme;i++)
for(int x=1;x<=a;x++)
for(int y=1;y<=b;y++){
add(pos(x,y,i,1),pos(x,y,i,0),1);
add(pos(x,y,i,0),pos(x,y,i,1),0);
if(i==tme)continue;
add(pos(x,y,i,0),pos(x,y,i+1,1),1);
add(pos(x,y,i+1,1),pos(x,y,i,0),0);
for(int j=0;j<4;j++){
if(otm(x+xx[j],y+yy[j]))continue;
add(pos(x,y,i,0),pos(x+xx[j],y+yy[j],i+1,1),1);
add(pos(x+xx[j],y+yy[j],i+1,1),pos(x,y,i,0),0);
}
}
for(int i=1;i<=n;i++){
add(0,pos(px[i],py[i],0,1),1);
add(pos(px[i],py[i],0,1),0,0);
add(pos(qx[i],qy[i],tme,0),t,1);
add(t,pos(qx[i],qy[i],tme,0),0);
}
return dinic()==n;
}
bool getans(int x,int y,int t,int lim){
if(t==lim){ax=x;ay=y;return true;}int np=pos(x,y,t,0);
for(int i=h[np];i;i=e[i].nxt){
if(e[i].w)continue;
if(e[i].v==pos(x,y,t+1,1)){ansl[t]='S';return getans(x,y,t+1,lim);}
if(e[i].v==pos(x,y-1,t+1,1)){ansl[t]='L';return getans(x,y-1,t+1,lim);}
if(e[i].v==pos(x,y+1,t+1,1)){ansl[t]='R';return getans(x,y+1,t+1,lim);}
if(e[i].v==pos(x-1,y,t+1,1)){ansl[t]='U';return getans(x-1,y,t+1,lim);}
if(e[i].v==pos(x+1,y,t+1,1)){ansl[t]='D';return getans(x+1,y,t+1,lim);}
}
return false;
}
bool print(int x,int ans){
getans(px[x],py[x],0,ans);
printf("%d %d %d %d ",px[x],py[x],ax,ay);
for(int i=0;i<ans;i++)putchar(ansl[i]);
putchar('\n');
return true;
}
int main(){
n=read();a=read();b=read();
for(int i=1;i<=n;i++){px[i]=read();py[i]=read();}
for(int i=1;i<=n;i++){qx[i]=read();qy[i]=read();}
int mx=a+b+n,np=0;
for(int i=lg(mx);i+1;i--){
if(np+(1<<i)>mx)continue;
if(!solve(np+(1<<i)))np+=(1<<i);
}
solve(++np);printf("%d\n",np);
for(int i=1;i<=n;i++)print(i,np);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1548kb
input:
3 4 4 1 1 1 4 4 4 1 3 2 3 2 4
output:
2 1 1 1 3 RR 1 4 2 3 DL 4 4 2 4 UU
result:
ok answer 2
Test #2:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
3 2 2 1 1 1 2 2 2 1 1 2 1 2 2
output:
1 1 1 1 1 S 1 2 2 2 D 2 2 2 1 L
result:
ok answer 1
Test #3:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
2 3 3 1 1 1 3 1 2 2 2
output:
2 1 1 1 2 RS 1 3 2 2 DL
result:
ok answer 2
Test #4:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
2 10 10 2 9 3 8 10 5 10 10
output:
10 2 9 10 10 DRDDDDDDDS 3 8 10 5 DDDDDDDLLL
result:
ok answer 10
Test #5:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
6 10 10 4 9 4 2 3 6 10 1 10 10 4 1 6 8 5 10 6 3 5 1 2 9 3 2
output:
5 4 9 6 8 RDDLL 4 2 3 2 RRLLU 3 6 2 9 RRRUS 10 1 5 1 UUUUU 10 10 5 10 UUUUU 4 1 6 3 RRDDS
result:
ok answer 5
Test #6:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
8 10 10 5 1 6 8 6 3 6 4 3 10 9 5 6 7 4 1 3 8 7 3 1 2 8 6 5 8 7 6 9 4 4 1
output:
4 5 1 7 3 RRDD 6 8 7 6 LLDS 6 3 4 1 UULL 6 4 9 4 SDDD 3 10 3 8 DLLU 9 5 8 6 RRLU 6 7 5 8 RRLU 4 1 1 2 RUUU
result:
ok answer 4
Test #7:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
1 10 10 8 3 8 4
output:
1 8 3 8 4 R
result:
ok answer 1
Test #8:
score: 0
Accepted
time: 0ms
memory: 5808kb
input:
1 10 10 10 1 6 6
output:
9 10 1 6 6 RRRRRUUUU
result:
ok answer 9
Test #9:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
8 10 10 7 8 4 6 10 9 4 7 4 3 10 6 3 3 2 7 3 7 2 10 3 8 1 9 6 1 3 10 10 2 6 4
output:
7 7 8 3 7 RLLUUUU 4 6 1 9 RRRUUUS 10 9 10 2 LLLLLLL 4 7 3 8 RRRLULS 4 3 6 1 RDDLLLS 10 6 6 4 UUUSLLU 3 3 3 10 RRRRRRR 2 7 2 10 RRRDDUU
result:
ok answer 7
Test #10:
score: 0
Accepted
time: 0ms
memory: 1756kb
input:
1 10 10 10 3 2 6
output:
11 10 3 2 6 RRRUUUUUUUU
result:
ok answer 11
Test #11:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
3 10 10 7 8 4 4 3 1 7 10 6 7 2 4
output:
5 7 8 7 10 RRDUS 4 4 6 7 RRRDD 3 1 2 4 RRRUS
result:
ok answer 5
Test #12:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
9 10 10 6 4 1 7 2 1 5 6 10 8 3 5 9 9 9 2 4 9 5 3 3 2 6 9 2 2 9 4 7 8 2 8 1 1 4 8
output:
5 6 4 3 2 UUULL 1 7 4 8 DDRDS 2 1 1 1 RRLLU 5 6 2 8 RRUUU 10 8 9 4 LLLLU 3 5 2 2 LUSLL 9 9 7 8 RLLUU 9 2 5 3 RUUUU 4 9 6 9 RDDLS
result:
ok answer 5
Test #13:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
2 10 10 9 8 3 3 5 8 4 9
output:
7 9 8 5 8 RLUUUUS 3 3 4 9 RRRRRRD
result:
ok answer 7
Test #14:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
8 10 10 10 5 8 4 2 8 2 4 10 8 6 6 1 7 10 1 8 6 10 5 10 2 5 9 8 10 10 4 3 9 4 2
output:
4 10 5 10 5 RLLR 8 4 10 4 RDDL 2 8 5 9 RDDD 2 4 4 2 DDLL 10 8 8 10 RRUU 6 6 8 6 RDDL 1 7 3 9 RRDD 10 1 10 2 RRLS
result:
ok answer 4
Test #15:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
1 10 10 1 9 2 10
output:
2 1 9 2 10 RD
result:
ok answer 2
Test #16:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
8 10 10 5 10 3 8 2 8 3 5 4 2 8 2 7 9 3 4 8 9 9 6 3 6 10 2 4 10 10 6 6 5 5 5
output:
6 5 10 8 9 DDDLSS 3 8 6 5 DDDLLL 2 8 4 10 DLRRRD 3 5 5 5 RDLRDL 4 2 10 2 DDDDDD 8 2 10 6 RRRRDD 7 9 9 6 DDLLSL 3 4 3 6 RRRRLL
result:
ok answer 6
Test #17:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1 10 10 8 6 1 8
output:
9 8 6 1 8 RRUUUUUUU
result:
ok answer 9
Test #18:
score: 0
Accepted
time: 0ms
memory: 1876kb
input:
10 10 10 7 10 4 4 9 10 5 7 10 7 4 1 1 5 6 7 6 4 5 3 5 7 1 9 1 6 8 3 5 1 10 8 2 6 4 2 3 10 3 1
output:
5 7 10 3 10 UUSUU 4 4 4 2 RLSLL 9 10 10 8 LLUDD 5 7 1 6 LUUUU 10 7 5 7 UUUUU 4 1 3 1 RRLLU 1 5 1 9 RRRRS 6 7 2 6 LUUUU 6 4 8 3 RDDLL 5 3 5 1 RLLLS
result:
ok answer 5
Test #19:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
7 10 10 4 5 1 5 6 5 9 6 5 5 9 3 1 10 10 6 6 2 5 1 2 7 8 1 7 10 6 3
output:
6 4 5 6 2 DDLLLS 1 5 2 7 RRDDUS 6 5 6 3 RRLLLL 9 6 8 1 LLLLLU 5 5 5 1 RLLLLL 9 3 10 6 RRRRDL 1 10 7 10 DDDDDD
result:
ok answer 6
Test #20:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
6 10 10 9 7 4 1 9 1 7 9 2 6 9 5 5 1 4 1 2 10 4 10 3 1 1 7
output:
8 9 7 1 7 UUUUUUUU 4 1 4 1 RRRRLLLL 9 1 3 1 RLUUUUUU 7 9 2 10 RLUUUURU 2 6 4 10 RRRRDDDU 9 5 5 1 LLLLUUUU
result:
ok answer 8
Test #21:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
10 10 10 7 7 8 6 10 3 6 2 10 8 1 10 9 5 1 2 8 3 10 9 8 9 8 10 6 4 7 8 4 3 3 5 3 9 6 1 8 7 10 2
output:
5 7 7 6 4 LLULS 8 6 8 7 LSRRS 10 3 10 2 RRLLL 6 2 6 1 RRLLL 10 8 7 8 RUULU 1 10 3 9 DDDLU 9 5 8 9 RRRRU 1 2 3 5 RRRDD 8 3 4 3 UUUUS 10 9 8 10 RLRUU
result:
ok answer 5
Test #22:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
10 10 10 2 9 1 2 3 9 6 9 3 3 9 2 2 4 5 8 1 6 4 9 1 10 6 10 3 6 2 5 4 2 7 3 10 2 9 1 2 9 5 8
output:
8 2 9 1 10 LLSRRRUS 1 2 4 2 RRDDDLLS 3 9 2 5 RLLSLLLU 6 9 7 3 DLLLLLLS 3 3 9 1 DDDDDDLL 9 2 10 2 RRRDLLLS 2 4 3 6 RRDRRLLS 5 8 5 8 RDDDLUUU 1 6 2 9 RRRRDDLU 4 9 6 10 RDDDDUUS
result:
ok answer 8
Test #23:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
10 10 10 10 6 9 2 7 7 7 3 6 8 5 4 2 10 1 1 5 9 4 6 5 1 9 9 9 1 7 6 3 2 4 8 7 7 9 7 3 1 6 10
output:
4 10 6 7 7 UUUR 9 2 9 1 RLLS 7 7 9 7 RDDL 7 3 5 1 LLUU 6 8 9 9 RDDD 5 4 3 2 LLUU 2 10 4 8 DDLL 1 1 3 1 RDDL 5 9 6 10 RDDU 4 6 7 6 DSDD
result:
ok answer 4
Test #24:
score: 0
Accepted
time: 0ms
memory: 2300kb
input:
10 1 100 1 17 1 49 1 12 1 37 1 83 1 44 1 75 1 78 1 72 1 3 1 75 1 47 1 55 1 81 1 6 1 59 1 17 1 68 1 28 1 24
output:
13 1 17 1 24 RRRRRRRRRRLLL 1 49 1 47 RRRRRLLLLLLLS 1 12 1 17 RRRRRRRRRLLLL 1 37 1 28 RRLLLLLLLLLLL 1 83 1 75 LLSRLLSLLLLLS 1 44 1 55 RRRRRRRRRRRRL 1 75 1 68 RRRLLLLLLLLLL 1 78 1 81 RRLLLRRRRRRLL 1 72 1 59 LLLLLLLLLLLLL 1 3 1 6 RRRRRRRRLLLLL
result:
ok answer 13
Test #25:
score: 0
Accepted
time: 1ms
memory: 2296kb
input:
10 1 100 1 43 1 75 1 59 1 42 1 26 1 33 1 88 1 7 1 24 1 95 1 68 1 31 1 39 1 74 1 66 1 67 1 28 1 70 1 86 1 58
output:
25 1 43 1 66 RRRRRRRRRRRRRRRRRRRRRRRRL 1 75 1 68 RRRRRRRRLLLLLLLSLLLLLLLLS 1 59 1 70 RRRRRRRRRRRRRRRRRRLLLLLLL 1 42 1 67 RRRRRRRRRRRRRRRRRRRRRRRRR 1 26 1 28 RRRRRRRRRRRRSLLLLLLLLSLLS 1 33 1 58 RRRRRRRRRRRRRRRRRRRRRRRRR 1 88 1 74 RRRRRLLLLLLLLLLLLLLLLLLLS 1 7 1 31 RRRRRRRRRRRRRRRRRRRRRRRRS 1 24 1 39 ...
result:
ok answer 25
Test #26:
score: 0
Accepted
time: 2ms
memory: 2344kb
input:
10 1 100 1 88 1 38 1 43 1 99 1 63 1 24 1 44 1 31 1 47 1 52 1 6 1 14 1 55 1 15 1 82 1 57 1 73 1 74 1 97 1 51
output:
23 1 88 1 74 RRRRLLLLLLLLLLLLLLLLLSL 1 38 1 15 LLLLLLLLLLLLLLLLLLLLLLL 1 43 1 51 LLLLLLRRRRRRRRRRRRRRRLS 1 99 1 97 RLRLRLRLRLRLRLRLRLRLLLS 1 63 1 82 RRRRRRRRRRRRRRRRRRRRRLL 1 24 1 6 RRLLLLLLLLLLLLLLLLLLLLS 1 44 1 55 RRRRRRRRRRRRRRRRRLLLLLL 1 31 1 14 RRLLLSLLLLLLLLLLLLLLLLS 1 47 1 57 RRRRRRRRRRRRRRRR...
result:
ok answer 23
Test #27:
score: -100
Wrong Answer
time: 4ms
memory: 5956kb
input:
10 100 1 6 1 96 1 41 1 76 1 97 1 72 1 94 1 82 1 23 1 40 1 31 1 33 1 84 1 77 1 41 1 24 1 39 1 68 1 8 1 82 1
output:
35 6 1 6 26 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLLLL 96 1 96 -11 LLLLLLLRRRRRRRRRRRLLLLLLLLLLLLLLLLS 41 1 41 -16 RRRRRRRRRLLLLLLLLLLLLLLLLLLLLLLLLLL 76 1 76 -34 LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL 97 1 97 -14 LSRRRRLRLRLRLRLRSLLLLLLLLLLLLLLLLLL 72 1 72 -32 RLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL 94 1 94 -16 ...
result:
wrong answer Integer parameter [name=ey_0] equals to 26, violates the range [1, 1]