oj.uz

답안 #63717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63717 2018-08-02T14:17:33 Z Bodo171 Tracks in the Snow (BOI13_tracks) C++14
80.3125 / 100
 2000 ms 387900 KB 
#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);
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]=" "+s[i];
    }
    dij(1,1);
    dij(n,m);
    cout<<mx+1;
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 6008 KB Output is correct
2 Correct 3 ms 6008 KB Output is correct
3 Correct 4 ms 6008 KB Output is correct
4 Correct 51 ms 6776 KB Output is correct
5 Correct 18 ms 6776 KB Output is correct
6 Correct 3 ms 6776 KB Output is correct
7 Correct 4 ms 6776 KB Output is correct
8 Correct 6 ms 6776 KB Output is correct
9 Correct 5 ms 6776 KB Output is correct
10 Correct 14 ms 6776 KB Output is correct
11 Correct 13 ms 6776 KB Output is correct
12 Correct 26 ms 6776 KB Output is correct
13 Correct 16 ms 6776 KB Output is correct
14 Correct 17 ms 6776 KB Output is correct
15 Correct 68 ms 7228 KB Output is correct
16 Correct 77 ms 7556 KB Output is correct
17 Correct 53 ms 7556 KB Output is correct
18 Correct 47 ms 8312 KB Output is correct

Subtask #2
50.3125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 33236 KB Output is correct
2 Correct 292 ms 33236 KB Output is correct
3 Correct 1619 ms 114176 KB Output is correct
4 Correct 476 ms 114176 KB Output is correct
5 Correct 1042 ms 114176 KB Output is correct
6 Execution timed out 2099 ms 188580 KB Time limit exceeded
7 Correct 40 ms 188580 KB Output is correct
8 Correct 48 ms 188580 KB Output is correct
9 Correct 13 ms 188580 KB Output is correct
10 Correct 6 ms 188580 KB Output is correct
11 Correct 45 ms 188580 KB Output is correct
12 Correct 9 ms 188580 KB Output is correct
13 Correct 311 ms 188580 KB Output is correct
14 Correct 177 ms 188580 KB Output is correct
15 Correct 141 ms 188580 KB Output is correct
16 Correct 117 ms 188580 KB Output is correct
17 Correct 732 ms 188580 KB Output is correct
18 Correct 568 ms 188580 KB Output is correct
19 Correct 483 ms 188580 KB Output is correct
20 Correct 380 ms 188580 KB Output is correct
21 Correct 958 ms 188580 KB Output is correct
22 Correct 1038 ms 188580 KB Output is correct
23 Correct 1505 ms 188580 KB Output is correct
24 Correct 886 ms 188580 KB Output is correct
25 Execution timed out 2041 ms 211768 KB Time limit exceeded
26 Execution timed out 2093 ms 292304 KB Time limit exceeded
27 Execution timed out 2067 ms 316500 KB Time limit exceeded
28 Execution timed out 2025 ms 316500 KB Time limit exceeded
29 Execution timed out 2061 ms 321884 KB Time limit exceeded
30 Execution timed out 2106 ms 339224 KB Time limit exceeded
31 Execution timed out 2040 ms 339224 KB Time limit exceeded
32 Execution timed out 2103 ms 387900 KB Time limit exceeded