Submission #1078285

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
struct eg{
  in dest,c,f,rev;
  in cost;
};
struct flow{
  vector<bool> vtd;
  vector<vector<eg> > egs;
  vector<vector<in> > ept;
  vector<in> dtt;
  in n,s,t,tot,inf;
  in totcost;
  void adegfl(eg& g, in c){
    g.f+=c;
    totcost+=c*g.cost;
    egs[g.dest][g.rev].f-=c;
    totcost-=c*egs[g.dest][g.rev].cost;
  }
  void adfl(in a, in b, in c){
    adegfl(egs[a][b],c);
  }
  void ini(in pn, in ps, in pt){
    totcost=0;
    n=pn;s=ps;t=pt;
    egs.resize(0);
    ept.resize(0);
    ept.resize(n,vector<in>(0));
    egs.resize(n,vector<eg>(0));
    dtt.resize(0);
    dtt.resize(n);
    tot=0;
    inf=1000000000LL;
    vtd.resize(n);
  }
  void add(in a, in b, double cst, in c1, in c2=0){
    assert(a>=0);
    assert(b>=0);
    assert(a<n);
    assert(b<n);
    eg ta,tb;
    ta.dest=b;
    tb.dest=a;
    ta.f=tb.f=0;
    ta.c=c1;
    tb.c=c2;
    ta.cost=cst;
    tb.cost=-cst;
    ta.rev=egs[b].size()+(a==b);
    tb.rev=egs[a].size();
    egs[a].push_back(ta);
    egs[b].push_back(tb);
  }
  pair<in,in> mincostmaxflow(){
    in totflow=0;
    VI capto,prev,costto,changed;
    capto.resize(n);
    prev.resize(n);
    costto.resize(n);
    changed.resize(n);
    while(1){
      forn(i,n){
	costto[i]=inf;
	prev[i]=-1;
	changed[i]=0;
	capto[i]=0;
      }
      capto[s]=inf;
      changed[s]=1;
      costto[s]=0;
      while(1){
	bool progress=0;
	forn(i,n){
	  if(!changed[i])
	    continue;
	  changed[i]=0;
	  forv(j,egs[i]){
	    eg& tp=egs[i][j];
	    if(tp.f<tp.c && costto[i]+tp.cost<costto[tp.dest]){
	      costto[tp.dest]=costto[i]+tp.cost;
	      changed[tp.dest]=1;
	      prev[tp.dest]=tp.rev;
	      capto[tp.dest]=min(capto[i],tp.c-tp.f);
	      progress=1;
	    }
	  }
	}
	if(!progress)
	  break;
      }
      if(prev[t]==-1)
	break;
      in d=capto[t];
      totflow+=d;
      in u=t;
      while(u!=s){
	adfl(egs[u][prev[u]].dest,egs[u][prev[u]].rev,d);
	u=egs[u][prev[u]].dest;
      }
    }
    assert(totcost%2==0);
    return MP(totflow,totcost/2);
  }
};

flow tfl;
VI dir,id;
VVI dr={{-1,0},{1,0},{0,-1},{0,1}};
string letter="UDLR";
VVI tpr;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  assert(n<=40);
  in a;
  in s=n*n+4*n;
  in t=s+1;
  tfl.ini(s+2,s,t);
  forn(i,n){
    forn(j,n){
      tfl.add(s,i*n+j,0,1);
    }
  }
  forn(z,4){
    forn(i,n){
      cin>>a;
      in cid=n*n+z*n+i;
      tfl.add(cid,t,0,a);
      dir.PB(z);
      id.PB(i);
      forn(j,n){
    	if(z<=1)
    	  tfl.add(j*n+i,cid,(z==0?j:(n-1-j)),1);
    	else
    	  tfl.add(i*n+j,cid,(z==2?j:(n-1-j)),1);
      }
    }
  }
  in totfl,totcst;
  tie(totfl,totcst)=tfl.mincostmaxflow();
  if(totfl!=n*n){
    cout<<"NO"<<endl;
    return 0;
  }
  tpr.resize(n,VI(n));
  forn(i,n){
    forn(j,n){
      forv(k,tfl.egs[i*n+j]){
    	if(tfl.egs[i*n+j][k].dest==s)
    	  continue;
    	if(tfl.egs[i*n+j][k].f==1)
    	  tpr[i][j]=tfl.egs[i*n+j][k].dest-n*n;
      }
    }
  }
  forn(i,n){
    forn(j,n){
      forn(k,j){
    	if(dir[tpr[i][k]]==3 && dir[tpr[i][j]]==2)
    	  swap(tpr[i][k],tpr[i][j]);
    	if(dir[tpr[k][i]]==1 && dir[tpr[j][i]]==0)
    	  swap(tpr[k][i],tpr[j][i]);
      }
    }
  }
  VVI don(n,VI(n));
  VVI fld(n,VI(n));
  queue<in> qx,qy;
  forn(i,n){
    if(!don[0][i] && dir[tpr[0][i]]==0){
      qx.push(0);
      qy.push(i);
      don[0][i]=1;
    }
    if(!don[n-1][i] && dir[tpr[n-1][i]]==1){
      qx.push(n-1);
      qy.push(i);
      don[n-1][i]=1;
    }
    if(!don[i][0] && dir[tpr[i][0]]==2){
      qx.push(i);
      qy.push(0);
      don[i][0]=1;
    }
    if(!don[i][n-1] && dir[tpr[i][n-1]]==3){
      qx.push(i);
      qy.push(n-1);
      don[i][n-1]=1;
    }
  }
  in u,v;
  while(!qx.empty()){
    u=qx.front();
    qx.pop();
    v=qy.front();
    qy.pop();
    assert(don[u][v]);
    cout<<letter[dir[tpr[u][v]]]<<id[tpr[u][v]]+1<<"\n";
    fld[u][v]=1;
    forn(i,4){
      bool flup=1;
      in tx=u;
      in ty=v;
      while(tx>=0 && tx<n && ty>=0 && ty<n){
    	flup&=fld[tx][ty];
    	tx+=dr[i][0];
    	ty+=dr[i][1];
      }
      if(flup){
    	tx=u;
    	ty=v;
    	in td=2*(i/2)+(1-(i%2));
    	while(tx>=0 && tx<n && ty>=0 && ty<n && fld[tx][ty]){
    	  tx+=dr[td][0];
    	  ty+=dr[td][1];
    	}
    	if(tx>=0 && tx<n && ty>=0 && ty<n && !don[tx][ty]){
    	  if(dir[tpr[tx][ty]]==i){
    	    don[tx][ty]=1;
    	    qx.push(tx);
    	    qy.push(ty);
    	  }
    	}
      }
    }
  }
  return 0;
}

Submission Info

Judge Result