CODE FESTIVAL 2016 Final

Submission #1078285

Source codeソースコード

#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

Task問題 J - Neue Spiel
User nameユーザ名 W4yneb0t
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 2000
Source lengthソースコード長 5095 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 2000 / 2000 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt,01-36.txt,01-37.txt,01-38.txt,01-39.txt,01-40.txt,01-41.txt,01-42.txt,01-43.txt,01-44.txt,01-45.txt,01-46.txt
dataset2 0 / 100 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt,01-36.txt,01-37.txt,01-38.txt,01-39.txt,01-40.txt,01-41.txt,01-42.txt,01-43.txt,01-44.txt,01-45.txt,01-46.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 3 ms 256 KB
01-02.txt AC 3 ms 256 KB
01-03.txt AC 3 ms 256 KB
01-04.txt AC 3 ms 384 KB
01-05.txt AC 9 ms 512 KB
01-06.txt AC 39 ms 896 KB
01-07.txt AC 135 ms 1536 KB
01-08.txt AC 132 ms 1536 KB
01-09.txt AC 7 ms 512 KB
01-10.txt AC 115 ms 1408 KB
01-11.txt AC 130 ms 1536 KB
01-12.txt AC 130 ms 1536 KB
01-13.txt AC 132 ms 1536 KB
01-14.txt AC 3 ms 256 KB
01-15.txt AC 98 ms 1280 KB
01-16.txt AC 135 ms 1536 KB
01-17.txt AC 136 ms 1536 KB
01-18.txt AC 134 ms 1536 KB
01-19.txt AC 120 ms 1408 KB
01-20.txt AC 135 ms 1536 KB
01-21.txt AC 136 ms 1536 KB
01-22.txt AC 135 ms 1408 KB
01-23.txt AC 150 ms 1536 KB
01-24.txt AC 152 ms 1536 KB
01-25.txt AC 151 ms 1536 KB
01-26.txt AC 29 ms 768 KB
01-27.txt AC 29 ms 768 KB
01-28.txt AC 133 ms 1408 KB
01-29.txt AC 150 ms 1536 KB
01-30.txt AC 151 ms 1536 KB
01-31.txt AC 147 ms 1536 KB
01-32.txt AC 148 ms 1536 KB
01-33.txt AC 146 ms 1536 KB
01-34.txt AC 150 ms 1536 KB
01-35.txt AC 103 ms 1536 KB
01-36.txt AC 117 ms 1536 KB
01-37.txt AC 90 ms 1536 KB
01-38.txt AC 116 ms 1408 KB
01-39.txt AC 130 ms 1536 KB
01-40.txt AC 128 ms 1408 KB
01-41.txt AC 139 ms 1536 KB
01-42.txt AC 137 ms 1536 KB
01-43.txt AC 121 ms 1536 KB
01-44.txt AC 126 ms 1536 KB
01-45.txt AC 121 ms 1536 KB
01-46.txt AC 126 ms 1536 KB
02-01.txt RE
02-02.txt RE
02-03.txt RE
02-04.txt RE
02-05.txt RE
02-06.txt RE
02-07.txt RE
02-08.txt RE
02-09.txt RE
02-10.txt RE
02-11.txt RE
02-12.txt RE
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB