QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#393707 | #6615. Cross the Maze | tz3528 | WA | 2ms | 14120kb | C++20 | 3.2kb | 2024-04-19 09:18:44 | 2024-04-19 09:18:44 |
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=1,r=2;
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,int flag){
// cout<<x<<' '<<y<<endl;
int u=num(k,x,y,flag);
if(u>num(a+b,a,b,1)) return ;
for(int i=fir[u];i;i=Next[i]){
if(v[i]) continue;
if(to[i]==num(k,x,y,1)) 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,0);}
if(to[i]==num(k+1,x,y+1,0)) {c.push_back('R');dfs1(x,y+1,k+1,0);}
if(to[i]==num(k+1,x-1,y,0)) {c.push_back('U');dfs1(x-1,y,k+1,0);}
if(to[i]==num(k+1,x,y-1,0)) {c.push_back('L');dfs1(x,y-1,k+1,0);}
}
}
int main(){
cin>>n>>a>>b;
s=0;t=num(a+b,a,b,1)+n+1;
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;
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,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: 0ms
memory: 13872kb
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: 2ms
memory: 14100kb
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: 2ms
memory: 13868kb
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: -100
Wrong Answer
time: 0ms
memory: 14120kb
input:
2 10 10 2 9 3 8 10 5 10 10
output:
3 2 9 2 9 PPP 3 8 3 8 PPP
result:
wrong answer ropes not match