oj.uz

Submission #63724

# Submission time Handle Problem Language Result Execution time Memory
63724 2018-08-02T14:35:19 Z Bodo171 Tracks in the Snow (BOI13_tracks) C++14
86.875 / 100
 2000 ms 108820 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();
              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});
                      }
                  }
              }
        }
        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;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4092 KB Output is correct
2 Correct 3 ms 4092 KB Output is correct
3 Correct 4 ms 4092 KB Output is correct
4 Correct 22 ms 4092 KB Output is correct
5 Correct 9 ms 4092 KB Output is correct
6 Correct 3 ms 4092 KB Output is correct
7 Correct 3 ms 4092 KB Output is correct
8 Correct 4 ms 4092 KB Output is correct
9 Correct 4 ms 4092 KB Output is correct
10 Correct 10 ms 4092 KB Output is correct
11 Correct 8 ms 4092 KB Output is correct
12 Correct 17 ms 4092 KB Output is correct
13 Correct 10 ms 4092 KB Output is correct
14 Correct 13 ms 4092 KB Output is correct
15 Correct 37 ms 5240 KB Output is correct
16 Correct 36 ms 5460 KB Output is correct
17 Correct 25 ms 5460 KB Output is correct
18 Correct 23 ms 5460 KB Output is correct

Subtask #2
56.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18004 KB Output is correct
2 Correct 136 ms 18004 KB Output is correct
3 Correct 1056 ms 98304 KB Output is correct
4 Correct 295 ms 98304 KB Output is correct
5 Correct 586 ms 98304 KB Output is correct
6 Execution timed out 2069 ms 108820 KB Time limit exceeded
7 Correct 19 ms 108820 KB Output is correct
8 Correct 17 ms 108820 KB Output is correct
9 Correct 7 ms 108820 KB Output is correct
10 Correct 4 ms 108820 KB Output is correct
11 Correct 24 ms 108820 KB Output is correct
12 Correct 5 ms 108820 KB Output is correct
13 Correct 162 ms 108820 KB Output is correct
14 Correct 98 ms 108820 KB Output is correct
15 Correct 100 ms 108820 KB Output is correct
16 Correct 89 ms 108820 KB Output is correct
17 Correct 427 ms 108820 KB Output is correct
18 Correct 386 ms 108820 KB Output is correct
19 Correct 276 ms 108820 KB Output is correct
20 Correct 220 ms 108820 KB Output is correct
21 Correct 649 ms 108820 KB Output is correct
22 Correct 710 ms 108820 KB Output is correct
23 Correct 781 ms 108820 KB Output is correct
24 Correct 769 ms 108820 KB Output is correct
25 Correct 1202 ms 108820 KB Output is correct
26 Correct 1652 ms 108820 KB Output is correct
27 Execution timed out 2070 ms 108820 KB Time limit exceeded
28 Execution timed out 2061 ms 108820 KB Time limit exceeded
29 Execution timed out 2059 ms 108820 KB Time limit exceeded
30 Execution timed out 2056 ms 108820 KB Time limit exceeded
31 Execution timed out 2020 ms 108820 KB Time limit exceeded
32 Correct 1953 ms 108820 KB Output is correct