oj.uz

답안 #63720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63720 2018-08-02T14:21:44 Z Bodo171 Tracks in the Snow (BOI13_tracks) C++14
86.875 / 100
 2000 ms 195572 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;getline(cin,s[0]);
    for(i=1;i<=n;i++)
    {
        getline(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 36 ms 5796 KB Output is correct
2 Correct 3 ms 5796 KB Output is correct
3 Correct 4 ms 5796 KB Output is correct
4 Correct 26 ms 6260 KB Output is correct
5 Correct 14 ms 6260 KB Output is correct
6 Correct 3 ms 6260 KB Output is correct
7 Correct 3 ms 6260 KB Output is correct
8 Correct 4 ms 6260 KB Output is correct
9 Correct 4 ms 6260 KB Output is correct
10 Correct 10 ms 6260 KB Output is correct
11 Correct 9 ms 6260 KB Output is correct
12 Correct 19 ms 6260 KB Output is correct
13 Correct 14 ms 6260 KB Output is correct
14 Correct 11 ms 6260 KB Output is correct
15 Correct 42 ms 6260 KB Output is correct
16 Correct 54 ms 6260 KB Output is correct
17 Correct 29 ms 6260 KB Output is correct
18 Correct 23 ms 6356 KB Output is correct

Subtask #2
56.875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 31376 KB Output is correct
2 Correct 175 ms 31376 KB Output is correct
3 Correct 1104 ms 96072 KB Output is correct
4 Correct 373 ms 96072 KB Output is correct
5 Correct 661 ms 96072 KB Output is correct
6 Execution timed out 2025 ms 159472 KB Time limit exceeded
7 Correct 34 ms 159472 KB Output is correct
8 Correct 31 ms 159472 KB Output is correct
9 Correct 8 ms 159472 KB Output is correct
10 Correct 6 ms 159472 KB Output is correct
11 Correct 34 ms 159472 KB Output is correct
12 Correct 5 ms 159472 KB Output is correct
13 Correct 171 ms 159472 KB Output is correct
14 Correct 103 ms 159472 KB Output is correct
15 Correct 86 ms 159472 KB Output is correct
16 Correct 78 ms 159472 KB Output is correct
17 Correct 466 ms 159472 KB Output is correct
18 Correct 434 ms 159472 KB Output is correct
19 Correct 263 ms 159472 KB Output is correct
20 Correct 246 ms 159472 KB Output is correct
21 Correct 762 ms 159472 KB Output is correct
22 Correct 850 ms 159472 KB Output is correct
23 Correct 939 ms 159472 KB Output is correct
24 Correct 549 ms 159472 KB Output is correct
25 Correct 1289 ms 159472 KB Output is correct
26 Correct 1904 ms 178368 KB Output is correct
27 Execution timed out 2043 ms 188244 KB Time limit exceeded
28 Execution timed out 2084 ms 188244 KB Time limit exceeded
29 Execution timed out 2077 ms 188244 KB Time limit exceeded
30 Execution timed out 2057 ms 188244 KB Time limit exceeded
31 Execution timed out 2050 ms 188244 KB Time limit exceeded
32 Correct 1893 ms 195572 KB Output is correct