QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#393729 | #6615. Cross the Maze | tz3528 | TL | 5ms | 16312kb | C++20 | 3.2kb | 2024-04-19 10:23:36 | 2024-04-19 10:23:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int p_max=110,q_max=1000100;
int n,a,b,s,t,edge=1,l,r;
int d[q_max],now[q_max],to[q_max],Next[q_max],fir[q_max];
int v[q_max],ans=0;
int x[p_max][2],y[p_max][2],h[p_max];
void add(int x,int y,int w){
to[++edge]=y; v[edge]=w; Next[edge]=fir[x]; fir[x]=edge;
to[++edge]=x; v[edge]=0; Next[edge]=fir[y]; fir[y]=edge;
}
bool bfs(){
for(int i=1;i<=t;i++) d[i]=0;
queue<int> q;
q.push(s);
d[s]=1;
now[s]=fir[s];
while(!q.empty()){
int x=q.front();q.pop();
for(int i=fir[x];i;i=Next[i]){
if(!d[to[i]]&&v[i]){//为分层且有权值的边才进行遍历
q.push(to[i]);
now[to[i]]=fir[to[i]];
d[to[i]]=d[x]+1;
if(to[i]==t) return true;
}
}
}
return false;
}
int dfs(int u,int flow){
if(u==t) return flow;
int rest=flow,k,i;
for(i=now[u];i&&rest;i=Next[i]){
if(v[i]&&d[to[i]]==d[u]+1){
k=dfs(to[i],min(rest,v[i]));//找最小流
if(!k) d[to[i]]=0;//剪枝,删掉已经增广过的点
v[i]-=k;
v[i^1]+=k;
rest-=k;//从u出发的点要消耗k
}
}
now[u]=i;//将u的下一个结点置空,避免重复
return flow-rest;//返回在u点的最大流出
}
int dinic(){
ans=0;
while(bfs()) ans+=dfs(s,1e9);
return ans;
}
int num(int k,int x,int y,int flag){return k*a*b+(x-1)*b+y+flag*(a+b+1)*a*b;}
bool check(int mid){
for(int i=0;i<=t;i++) fir[i]=0;
edge=1;
for(int i=1;i<=n;i++) add(s,num(0,x[i][0],y[i][0],0),1);
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
for(int k=0;k<mid;k++){
add(num(k,i,j,0),num(k,i,j,1),1);
add(num(k,i,j,1),num(k+1,i,j,0),1);
if(i>1) add(num(k,i,j,1),num(k+1,i-1,j,0),1);
if(j>1) add(num(k,i,j,1),num(k+1,i,j-1,0),1);
if(i<a) add(num(k,i,j,1),num(k+1,i+1,j,0),1);
if(j<b) add(num(k,i,j,1),num(k+1,i,j+1,0),1);
}
add(num(mid,i,j,0),num(mid,i,j,1),1);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=mid;j++){
add(num(j,x[i][1],y[i][1],1),num(mid,a,b,1)+i,1);
}
add(num(mid,a,b,1)+i,t,1);
}
return dinic()==n;
}
vector<char> c;
void dfs1(int x,int y,int k){
// cout<<x<<' '<<y<<endl;
int u=num(k,x,y,1);
if(u>num(l,a,b,1)) return ;
for(int i=fir[u];i;i=Next[i]){
if(v[i]) continue;
if(to[i]==num(k+1,x,y,0)) {c.push_back('P');dfs1(x,y,k+1);}
if(to[i]==num(k+1,x+1,y,0)) {c.push_back('D');dfs1(x+1,y,k+1);}
if(to[i]==num(k+1,x,y+1,0)) {c.push_back('R');dfs1(x,y+1,k+1);}
if(to[i]==num(k+1,x-1,y,0)) {c.push_back('U');dfs1(x-1,y,k+1);}
if(to[i]==num(k+1,x,y-1,0)) {c.push_back('L');dfs1(x,y-1,k+1);}
}
}
int main(){
cin>>n>>a>>b;
s=0;t=num(a+b,a,b,1)+n+1;
l=0,r=a+b;
for(int i=1;i<=n;i++) cin>>x[i][0]>>y[i][0];
for(int i=1;i<=n;i++) cin>>x[i][1]>>y[i][1];
while(l<=r){
int mid=(l+r)/2;
if(check(mid)) r=mid-1;
else l=mid+1;
}
cout<<l<<endl;
check(l);
int u=num(0,x[1][0],y[1][0],0);
for(int i=1;i<=n;i++){
int j=0;
c.clear();
dfs1(x[i][0],y[i][0],0);
cout<<x[i][0]<<' '<<y[i][0]<<' ';
for(auto it:c){
if(it=='U') x[i][0]--;
if(it=='D') x[i][0]++;
if(it=='L') y[i][0]--;
if(it=='R') y[i][0]++;
}
cout<<x[i][0]<<' '<<y[i][0]<<' ';
for(auto it:c) cout<<it,j++;
while(j<l) cout<<'P',j++;
cout<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 14112kb
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: 0ms
memory: 13868kb
input:
3 2 2 1 1 1 2 2 2 1 1 2 1 2 2
output:
1 1 1 1 1 P 1 2 2 2 D 2 2 2 1 L
result:
ok answer 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 13760kb
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: 14120kb
input:
2 10 10 2 9 3 8 10 5 10 10
output:
10 2 9 10 10 DRDDDDDDDP 3 8 10 5 DDDDDDDLLL
result:
ok answer 10
Test #5:
score: 0
Accepted
time: 2ms
memory: 13912kb
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 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: 1ms
memory: 13888kb
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 DLPP 4 1 1 2 RUUU
result:
ok answer 4
Test #7:
score: 0
Accepted
time: 1ms
memory: 13920kb
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: 2ms
memory: 13904kb
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: 0ms
memory: 13852kb
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 DDDLLPP 2 7 1 9 DURRUPP
result:
ok answer 7
Test #10:
score: 0
Accepted
time: 2ms
memory: 13944kb
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: 13916kb
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: 2ms
memory: 13820kb
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: 0ms
memory: 15968kb
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: 0ms
memory: 13896kb
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 DDLL 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: 1ms
memory: 15972kb
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: 2ms
memory: 13956kb
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 DLLPPP 3 5 6 5 RDLDDP 4 2 10 2 DDDDDD 8 2 10 6 DDRRRR 7 9 9 6 DDLLLP 3 4 5 5 RDDPPP
result:
ok answer 6
Test #17:
score: 0
Accepted
time: 1ms
memory: 14120kb
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: 13916kb
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 DLLPP 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 DDLPP 5 3 5 1 LLPPP
result:
ok answer 5
Test #19:
score: 0
Accepted
time: 2ms
memory: 16168kb
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 5 1 DLLLLP 1 5 2 7 RRDPPP 6 5 6 3 LLPPPP 9 6 10 6 DPPPPP 5 5 6 2 DLLLPP 9 3 8 1 LLUPPP 1 10 7 10 DDDDDD
result:
ok answer 6
Test #20:
score: 0
Accepted
time: 2ms
memory: 14080kb
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: 0ms
memory: 13912kb
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 DDLPP 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: 2ms
memory: 13864kb
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 9 1 DLDDDDDL 9 2 10 2 DPPPPPPP 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: 2ms
memory: 13924kb
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 9 9 DRDD 5 4 3 2 LLUU 2 10 4 8 DDLL 1 1 3 1 DDPP 5 9 6 10 RDPP 4 6 7 6 DDDP
result:
ok answer 4
Test #24:
score: 0
Accepted
time: 0ms
memory: 16312kb
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: 5ms
memory: 16076kb
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: 4ms
memory: 16072kb
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 57 RRRRRRRRRRRRRRPPPPPPPPP 1 99 1 97 LLPPPPPPPPPPPPPPPPPPPPP 1 63 1 74 LLLLLLRRRRRRRRRRRRRRRRR 1 24 1 6 LLLLLLLLLLLLLLLLLLPPPPP 1 44 1 51 RRRRRRRPPPPPPPPPPPPPPPP 1 31 1 14 LLLLLLLLLLLLLLLLLPPPPPP 1 47 1 55 RRRRRRRRPPPPPPPP...
result:
ok answer 23
Test #27:
score: -100
Time Limit Exceeded
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 9 4 DDRRDRPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 96 1 -524191 -524286 UUUUUUUUUUUUUUUUUUULLULLUULLULLUUULLULLUULLULLUUUULLULLUULLULLUUULLULLUULLULLUUUUULLULLUULLULLUUULLULLUULLULLUUUULLULLUULLULLUUULLULLUULLULLUUUUUULLULLUULLULLUUULLULLUULLULLUUUULLULLUULLULLUUULLULLUULLULLUUUUULLULLUULLULLUUULLULLUUL...