QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#393656 | #6615. Cross the Maze | tz3528 | TL | 0ms | 0kb | C++20 | 3.0kb | 2024-04-19 01:37:53 | 2024-04-19 01:37:55 |
answer
#include<bits/stdc++.h>
using namespace std;
const int p_max=110,q_max=1000100;
int n,a,b,s,t,edge=1;
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;//剪枝,删掉已经增广过的点
h[u]=to[i];
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;
}
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];
int l=1,r=1;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)) r=mid-1;
else l=mid+1;
}
cout<<l<<endl;
for(int i=1;i<=1;i++){
int u=num(0,x[i][0],y[i][0],0),j=0;
vector<char> c;
int p0,q0,p1,q1;
p0=(u-1)%(a*b)+1;
q0=(p0-1)%b+1;
p0=(p0-1)/b+1;
cout<<p0<<' '<<q0<<' ';
while(h[u]<=num(l,a,b,1)){
p0=(u-1)%(a*b)+1;
q0=(p0-1)%b+1;p0=(p0-1)/b+1;
u=h[u];u=h[u];
if(u>num(l,a,b,1)) break;
p1=(u-1)%(a*b)+1;
q1=(p1-1)%b+1;p1=(p1-1)/b+1;
if(p0+1==p1) c.push_back('D');
if(p0-1==p1) c.push_back('U');
if(q0+1==q1) c.push_back('R');
if(q0-1==q1) c.push_back('L');
if(p0==p1&&q0==q1) c.push_back('P');
j++;
// cout<<p0<<' '<<q0<<' '<<p1<<' '<<q1<<endl;
}
cout<<p0<<' '<<q0<<' ';
while(j<l) j++,c.push_back('P');
for(auto it:c) cout<<it;
cout<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 4 4 1 1 1 4 4 4 1 3 2 3 2 4
output:
2