Submission #63728

#	Time	Username	Problem	Language	Result	Execution time	Memory
63728		Bodo171	Tracks in the Snow (BOI13_tracks)	C++14	86.88 / 100	2099 ms	209816 KiB

tracks

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=4005;
int d[nmax][nmax];
pair<int,int> q[2][nmax*nmax];
string s[nmax];
int p[2],u[2];
bool E[nmax][nmax];
int use,mx,i,j,dd,n,m,li,ci,lf,cf,di;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
void dij(int L,int C)
{
    p[0]=p[1]=1;
    u[0]=u[1]=0;
    q[0][++u[0]]={L,C};use=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
           d[i][j]=n*m+1,E[i][j]=0;
    d[L][C]=0;
    for(i=0;i<=n*m;i++)
    {
        if(p[use]>u[use])
            return;
        mx=max(mx,i);
        for(p[use]=1;p[use]<=u[use];p[use]++)
        {
             li=q[use][p[use]].first;ci=q[use][p[use]].second;
             if(!E[li][ci])
              for(di=0;di<4;di++)
              {
                  lf=li+d1[di];cf=ci+d2[di];
                  if(lf>=1&&cf>=1&&lf<=n&&cf<=m&&(s[lf][cf]=='R'||s[lf][cf]=='F'))
                  {
                      dd=d[li][ci]+(s[li][ci]!=s[lf][cf]);
                      if(dd<d[lf][cf])
                      {
                          d[lf][cf]=dd;
                          q[(dd&1)][++u[(dd&1)]]={lf,cf};
                      }
                  }
              }
             E[li][ci]=1;
        }
        p[use]=1;u[use]=0;
        use=1-use;
    }
}
int main()
{
   // freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;getline(cin,s[0]);
    for(i=1;i<=n;i++)
    {
        getline(cin,s[i]);
        s[i]=" "+s[i];
    }
    dij(1,1);
    cout<<mx+1;
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 56.875 / 70