QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410153 | #6615. Cross the Maze | Siilhouette | WA | 13ms | 9180kb | C++23 | 3.9kb | 2024-05-13 16:42:04 | 2024-05-13 16:42:04 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include<set>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int N=200010;
const int M=200010;
const int inf=1000000000;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,-1,1};
int n,m,q,st,ed,tot=1,head[N],d[N],cur[N];
vector<pair<int,int> >stx,edx;
vector<int>c[110];
struct Edge{
int ver,suiv,edge;
char dir;
}e[M<<1];
inline void _lnk(int x,int y,int z,char ch)
{
e[++tot].ver=y;
e[tot].edge=z;
e[tot].suiv=head[x];
head[x]=tot;
e[tot].dir=ch;
}
inline void lnk(int x,int y,int z,char ch)
{
_lnk(x,y,z,ch),_lnk(y,x,0,ch);
}
inline int dfs(int x,int flow)
{
if(x==ed)return flow;
int minflow,resflow=0;
for(int &i=cur[x];i;i=e[i].suiv)
//for(int i=head[x];i;i=e[i].suiv)
{
int y=e[i].ver;
if(d[y]!=d[x]+1||!e[i].edge)continue;
minflow=dfs(y,min(flow,e[i].edge));
flow-=minflow;
e[i].edge-=minflow;
resflow+=minflow;
e[i^1].edge+=minflow;
if(!flow)break;
}
if(!resflow)d[x]=-1;
return resflow;
}
inline bool bfs()
{
memset(d,-1,sizeof(d));
queue<int>q;
q.push(st);
d[st]=0;
while(q.size())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].suiv)
{
int y=e[i].ver;
if(~d[y]||!e[i].edge)continue;
d[y]=d[x]+1;
q.push(y);
}
}
return ~d[ed];
}
inline ll dinic()
{
ll res=0;
while(bfs())
{
memcpy(cur,head,sizeof(head));
res+=1ll*dfs(st,inf);
}
return res;
}
inline int _(int dep,int op,int x,int y)
{
return ((dep-1)*2+op)*n*m+(x-1)*n+y;
}
inline void dfs1(int x,int id)
{
//cout<<"dfs1 "<<x<<" "<<id<<endl;
if(x==ed)return;
for(int i=head[x];i;i=e[i].suiv)
{
int y=e[i].ver,z=e[i].edge;
if((i&1)||z)continue;
if(e[i].dir!=0)c[id].push_back(e[i].dir)
//,cout<<"id "<<id<<" "<<char(e[i].dir)<<endl
;
dfs1(y,id);
}
}
inline bool valid(int mid)
{
tot=1;
memset(head,0,sizeof(head));
st=0,ed=N-1;
for(auto pos:stx)
lnk(st,_(1,0,pos.first,pos.second),1,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
lnk(_(1,0,i,j),_(1,1,i,j),1,0);
for(int i=1;i<=q;i++)
lnk(N-1-i,ed,1,0);
for(int i=1;i<=q;i++)
lnk(_(1,1,edx[i-1].first,edx[i-1].second),N-1-i,1,0);
int ans=0;
for(int i=1;i<=mid;i++)
{
for(int j=1;j<=n;j++)
for(int k=1;k<=m;k++)
{
for(int l=0;l<4;l++)
{
int posx=j+dx[l],posy=k+dy[l];
if(posx<1||posx>n||posy<1||posy>m)continue;
char ch;
if(dx[l]==0&&dy[l]==1)ch='R';
else if(dx[l]==0&&dy[l]==-1)ch='L';
else if(dx[l]==-1&&dy[l]==0)ch='U';
else ch='D';
//cout<<"lnk "<<ch<<endl;
lnk(_(i,1,j,k),_(i+1,0,posx,posy),1,ch);
}
lnk(_(i+1,0,j,k),_(i+1,1,j,k),1,0);
}
for(int j=1;j<=q;j++)
lnk(_(i+1,1,edx[j-1].first,edx[j-1].second),N-1-j,1,0);
}
return dinic()>=q;
}
signed main()
{
scanf("%d%d%d",&q,&n,&m);
for(int i=1,x,y;i<=q;i++)
scanf("%d%d",&x,&y),stx.push_back(make_pair(x,y));
for(int i=1,x,y;i<=q;i++)
scanf("%d%d",&x,&y),edx.push_back(make_pair(x,y));
//dinic();
//cout<<maxflow<<endl;
//ans=3;
//cout<<valid(1)<<endl;
int l=1,r=n*m,ans=-1;
while(l<=r)
{
int mid=l+r>>1;
//cout<<"valid "<<mid<<endl;
if(valid(mid))r=mid-1,ans=mid
//,cout<<"ok"<<endl
;
else l=mid+1
//,cout<<"no"<<endl
;
}
valid(ans);
printf("%d\n",ans);
for(int i=1;i<=q;i++)
dfs1(_(1,0,stx[i-1].first,stx[i-1].second),i);
for(int i=1;i<=q;i++)
{
printf("%d %d ",stx[i-1].first,stx[i-1].second);
int posx=stx[i-1].first,posy=stx[i-1].second;
for(int j=1,lim=c[i].size();j<=lim;j++)
{
if(c[i][j-1]=='R')posy+=1;
if(c[i][j-1]=='L')posy-=1;
if(c[i][j-1]=='U')posx-=1;
if(c[i][j-1]=='D')posx+=1;
}
printf("%d %d ",posx,posy);
for(int j=1,lim=c[i].size();j<=ans;j++)
printf("%c",j<=lim?c[i][j-1]:'P');
putchar('\n');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 6256kb
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 LD 4 4 2 4 UU
result:
ok answer 2
Test #2:
score: 0
Accepted
time: 2ms
memory: 6128kb
input:
3 2 2 1 1 1 2 2 2 1 1 2 1 2 2
output:
1 1 1 2 1 D 1 2 1 1 L 2 2 2 2 P
result:
ok answer 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 6184kb
input:
2 3 3 1 1 1 3 1 2 2 2
output:
2 1 1 2 2 DR 1 3 1 2 LP
result:
ok answer 2
Test #4:
score: 0
Accepted
time: 2ms
memory: 6900kb
input:
2 10 10 2 9 3 8 10 5 10 10
output:
10 2 9 10 10 DRDDDDDDDP 3 8 10 5 LLLDDDDDDD
result:
ok answer 10
Test #5:
score: 0
Accepted
time: 3ms
memory: 6908kb
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 RDLLD 4 2 3 2 UPPPP 3 6 2 9 RRRUP 10 1 5 1 UUUUU 10 10 5 10 UUUUU 4 1 6 3 DRRDP
result:
ok answer 5
Test #6:
score: 0
Accepted
time: 4ms
memory: 7204kb
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 4 1 UPPP 6 8 5 8 UPPP 6 3 7 3 DPPP 6 4 8 6 RRDD 3 10 3 8 LLPP 9 5 9 4 LPPP 6 7 7 6 LDPP 4 1 1 2 RUUU
result:
ok answer 4
Test #7:
score: 0
Accepted
time: 3ms
memory: 6852kb
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: 6888kb
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: 12ms
memory: 7208kb
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 2 10 RRUUUUU 4 6 3 10 RRRRUPP 10 9 10 2 LLLLLLL 4 7 3 8 RUPPPPP 4 3 3 7 RDRRRUU 10 6 6 4 LLUUUUP 3 3 6 1 LLDDDPP 2 7 1 9 DURRUPP
result:
ok answer 7
Test #10:
score: 0
Accepted
time: 0ms
memory: 7188kb
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: 0ms
memory: 9180kb
input:
3 10 10 7 8 4 4 3 1 7 10 6 7 2 4
output:
5 7 8 7 10 RRPPP 4 4 6 7 RRRDD 3 1 2 4 RRRUP
result:
ok answer 5
Test #12:
score: 0
Accepted
time: 9ms
memory: 6916kb
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 LULUU 1 7 2 8 RDPPP 2 1 1 1 RLUPP 5 6 5 3 LLLPP 10 8 7 8 UUUPP 3 5 2 2 LLLUP 9 9 6 9 UUUPP 9 2 9 4 RRPPP 4 9 4 8 LPPPP
result:
ok answer 5
Test #13:
score: 0
Accepted
time: 4ms
memory: 8788kb
input:
2 10 10 9 8 3 3 5 8 4 9
output:
7 9 8 5 8 UUUUPPP 3 3 4 9 RRRRRRD
result:
ok answer 7
Test #14:
score: 0
Accepted
time: 2ms
memory: 6868kb
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 PPPP 8 4 10 4 DDPP 2 8 5 9 RDDD 2 4 4 2 LLDD 10 8 8 10 RRUU 6 6 8 6 DDPP 1 7 3 9 RRDD 10 1 10 2 RPPP
result:
ok answer 4
Test #15:
score: 0
Accepted
time: 0ms
memory: 6896kb
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: 6ms
memory: 8312kb
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 4 10 UPPPPP 3 8 8 9 RDDDDD 2 8 3 6 LLDPPP 3 5 6 5 RLDDDP 4 2 10 2 DDDDDD 8 2 10 6 DDRRRR 7 9 9 6 DLLLDP 3 4 5 5 RDDPPP
result:
ok answer 6
Test #17:
score: 0
Accepted
time: 3ms
memory: 7200kb
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: 8ms
memory: 6920kb
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 UUUUP 4 4 3 1 LLLUP 9 10 10 8 LLDPP 5 7 1 6 LUUUU 10 7 5 7 UUUUU 4 1 4 2 RPPPP 1 5 1 9 RRRRP 6 7 2 6 ULUUU 6 4 8 3 LDDPP 5 3 5 1 LLPPP
result:
ok answer 5
Test #19:
score: 0
Accepted
time: 7ms
memory: 8892kb
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 LLLDDP 1 5 2 7 RRDPPP 6 5 6 3 LLPPPP 9 6 10 6 DPPPPP 5 5 5 1 LLLLPP 9 3 8 1 LLUPPP 1 10 7 10 DDDDDD
result:
ok answer 6
Test #20:
score: 0
Accepted
time: 3ms
memory: 6852kb
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 4 10 RRRUUUUU 4 1 4 1 PPPPPPPP 9 1 3 1 UUUUUUPP 7 9 2 10 RUUUUUPP 2 6 1 7 RUPPPPPP 9 5 5 1 LLLLUUUU
result:
ok answer 8
Test #21:
score: 0
Accepted
time: 9ms
memory: 9056kb
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 7 8 RPPPP 8 6 8 7 RPPPP 10 3 10 2 LPPPP 6 2 6 1 LPPPP 10 8 8 10 RRUUP 1 10 3 9 LDDPP 9 5 6 4 LUUUP 1 2 3 5 RDDRR 8 3 4 3 UUUUP 10 9 8 9 UUPPP
result:
ok answer 5
Test #22:
score: 0
Accepted
time: 11ms
memory: 6916kb
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 2 9 PPPPPPPP 1 2 7 3 RDDDDDDP 3 9 1 10 RUUPPPPP 6 9 6 10 RPPPPPPP 3 3 10 2 LDDDDDDD 9 2 9 1 LPPPPPPP 2 4 2 5 RPPPPPPP 5 8 5 8 PPPPPPPP 1 6 3 6 DDPPPPPP 4 9 4 2 LLLLLLLP
result:
ok answer 8
Test #23:
score: 0
Accepted
time: 10ms
memory: 6864kb
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 9 7 RUPP 9 2 9 1 LPPP 7 7 7 7 PPPP 7 3 5 1 LLUU 6 8 7 6 LLDP 5 4 3 2 LLUU 2 10 6 10 DDDD 1 1 3 1 DDPP 5 9 9 9 DDDD 4 6 4 8 RRPP
result:
ok answer 4
Test #24:
score: 0
Accepted
time: 7ms
memory: 6668kb
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 17 PPPPPPPPPPPPP 1 49 1 47 LLPPPPPPPPPPP 1 12 1 24 RRRRRRRRRRRRP 1 37 1 28 LLLLLLLLLPPPP 1 83 1 81 LLPPPPPPPPPPP 1 44 1 55 RRRRRRRRRRRPP 1 75 1 75 PPPPPPPPPPPPP 1 78 1 68 LLLLLLLLLLPPP 1 72 1 59 LLLLLLLLLLLLL 1 3 1 6 RRRPPPPPPPPPP
result:
ok answer 13
Test #25:
score: 0
Accepted
time: 10ms
memory: 6656kb
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 RRRRRRRRRRRRRRRRRRRRRRRPP 1 75 1 74 LPPPPPPPPPPPPPPPPPPPPPPPP 1 59 1 68 LRRRRRRRRRRPPPPPPPPPPPPPP 1 42 1 67 RRRRRRRRRRRRRRRRRRRRRRRRR 1 26 1 28 RRPPPPPPPPPPPPPPPPPPPPPPP 1 33 1 58 RRRRRRRRRRRRRRRRRRRRRRRRR 1 88 1 86 LLPPPPPPPPPPPPPPPPPPPPPPP 1 7 1 31 RRRRRRRRRRRRRRRRRRRRRRRRP 1 24 1 39 ...
result:
ok answer 25
Test #26:
score: 0
Accepted
time: 13ms
memory: 6960kb
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 82 LLLLLLPPPPPPPPPPPPPPPPP 1 38 1 15 LLLLLLLLLLLLLLLLLLLLLLL 1 43 1 51 RRRRRRRRPPPPPPPPPPPPPPP 1 99 1 97 LLPPPPPPPPPPPPPPPPPPPPP 1 63 1 73 LLLLLLRRRRRRRRRRRRRRRRP 1 24 1 6 LLLLLLLLLLLLLLLLLLPPPPP 1 44 1 57 RRRRRRRRRRRRRPPPPPPPPPP 1 31 1 14 LLLLLLLLLLLLLLLLLPPPPPP 1 47 1 55 RRRRRRRRPPPPPPPP...
result:
ok answer 23
Test #27:
score: -100
Wrong Answer
time: 3ms
memory: 6724kb
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:
17 6 1 7 1 DPPPPPPPPPPPPPPPP 96 1 96 1 PPPPPPPPPPPPPPPPP 41 1 41 1 PPPPPPPPPPPPPPPPP 76 1 76 1 PPPPPPPPPPPPPPPPP 97 1 97 1 PPPPPPPPPPPPPPPPP 72 1 72 1 PPPPPPPPPPPPPPPPP 94 1 94 1 PPPPPPPPPPPPPPPPP 82 1 82 1 PPPPPPPPPPPPPPPPP 23 1 24 1 DPPPPPPPPPPPPPPPP 40 1 40 1 PPPPPPPPPPPPPPPPP
result:
wrong answer ropes not match