oj.uz

Submission #63726

# Submission time Handle Problem Language Result Execution time Memory
63726 2018-08-02T14:37:11 Z Bodo171 Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 119436 KB 
#include <iostream>
#include <fstream>
#include <queue>
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)
{

    queue< pair<int,int> > q[2];
    q[0].push({L,C});
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
           d[i][j]=n*m+1;
    d[L][C]=0;
    for(i=0;i<=n*m;i++)
    {
        if(q[use].empty())
            return;
        mx=max(mx,i);
        while(!q[use].empty())
        {
             li=q[use].front().first;ci=q[use].front().second;q[use].pop();
             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-1]=='R'||s[lf][cf-1]=='F'))
                  {
                      dd=d[li][ci]+(s[li][ci-1]!=s[lf][cf-1]);
                      if(dd<d[lf][cf])
                      {
                          d[lf][cf]=dd;
                          q[(dd&1)].push({lf,cf});
                      }
                  }
              }
              E[li][ci]=1;
        }
        p[use]=1;u[use]=0;
        use=1-use;
    }
}
int main()
{
   // freopen("data.in","r",stdin);
    cin>>n>>m;getline(cin,s[0]);
    for(i=1;i<=n;i++)
    {
        getline(cin,s[i]);
    }
    dij(1,1);
    cout<<mx+1;
    return 0;
}

Compilation message

tracks.cpp: In function 'void dij(int, int)':
tracks.cpp:31:14: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
              if(!E[li][ci])
              ^~
tracks.cpp:45:15: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
               E[li][ci]=1;
               ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5752 KB Output is correct
2 Correct 3 ms 5752 KB Output is correct
3 Correct 4 ms 5752 KB Output is correct
4 Correct 34 ms 5752 KB Output is correct
5 Correct 10 ms 5752 KB Output is correct
6 Correct 4 ms 5752 KB Output is correct
7 Correct 3 ms 5752 KB Output is correct
8 Correct 4 ms 5752 KB Output is correct
9 Correct 3 ms 5752 KB Output is correct
10 Correct 9 ms 5752 KB Output is correct
11 Correct 10 ms 5752 KB Output is correct
12 Correct 19 ms 5752 KB Output is correct
13 Correct 11 ms 5752 KB Output is correct
14 Correct 12 ms 5752 KB Output is correct
15 Correct 38 ms 6096 KB Output is correct
16 Correct 39 ms 6096 KB Output is correct
17 Correct 27 ms 6096 KB Output is correct
18 Correct 26 ms 6096 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 31208 KB Output is correct
2 Correct 146 ms 31208 KB Output is correct
3 Correct 1061 ms 109416 KB Output is correct
4 Correct 282 ms 109416 KB Output is correct
5 Correct 628 ms 109416 KB Output is correct
6 Execution timed out 2066 ms 118780 KB Time limit exceeded
7 Correct 39 ms 118780 KB Output is correct
8 Correct 37 ms 118780 KB Output is correct
9 Correct 7 ms 118780 KB Output is correct
10 Correct 6 ms 118780 KB Output is correct
11 Correct 32 ms 118780 KB Output is correct
12 Correct 6 ms 118780 KB Output is correct
13 Correct 146 ms 118780 KB Output is correct
14 Correct 89 ms 118780 KB Output is correct
15 Correct 121 ms 118780 KB Output is correct
16 Correct 68 ms 118780 KB Output is correct
17 Correct 492 ms 118780 KB Output is correct
18 Correct 440 ms 118780 KB Output is correct
19 Correct 297 ms 118780 KB Output is correct
20 Correct 256 ms 118780 KB Output is correct
21 Correct 674 ms 118780 KB Output is correct
22 Correct 763 ms 118780 KB Output is correct
23 Correct 833 ms 118780 KB Output is correct
24 Correct 634 ms 118780 KB Output is correct
25 Correct 1423 ms 118780 KB Output is correct
26 Correct 1951 ms 118780 KB Output is correct
27 Execution timed out 2062 ms 118780 KB Time limit exceeded
28 Execution timed out 2081 ms 119436 KB Time limit exceeded
29 Execution timed out 2078 ms 119436 KB Time limit exceeded
30 Execution timed out 2073 ms 119436 KB Time limit exceeded
31 Execution timed out 2072 ms 119436 KB Time limit exceeded
32 Execution timed out 2071 ms 119436 KB Time limit exceeded