oj.uz

답안 #63723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63723 2018-08-02T14:31:36 Z Bodo171 Tracks in the Snow (BOI13_tracks) C++14
86.875 / 100
 2000 ms 209228 KB 
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
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;
              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)][++u[(dd&1)]]={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

# 결과 실행 시간 메모리 Grader output
1 Correct 47 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 32 ms 6384 KB Output is correct
5 Correct 12 ms 6384 KB Output is correct
6 Correct 3 ms 6384 KB Output is correct
7 Correct 3 ms 6384 KB Output is correct
8 Correct 4 ms 6384 KB Output is correct
9 Correct 3 ms 6384 KB Output is correct
10 Correct 10 ms 6384 KB Output is correct
11 Correct 8 ms 6384 KB Output is correct
12 Correct 16 ms 6384 KB Output is correct
13 Correct 14 ms 6384 KB Output is correct
14 Correct 13 ms 6384 KB Output is correct
15 Correct 36 ms 6384 KB Output is correct
16 Correct 41 ms 6384 KB Output is correct
17 Correct 34 ms 6384 KB Output is correct
18 Correct 24 ms 6532 KB Output is correct

Subtask #2
56.875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 31380 KB Output is correct
2 Correct 184 ms 31380 KB Output is correct
3 Correct 1233 ms 109588 KB Output is correct
4 Correct 310 ms 109588 KB Output is correct
5 Correct 697 ms 109588 KB Output is correct
6 Execution timed out 2091 ms 188492 KB Time limit exceeded
7 Correct 32 ms 188492 KB Output is correct
8 Correct 27 ms 188492 KB Output is correct
9 Correct 9 ms 188492 KB Output is correct
10 Correct 5 ms 188492 KB Output is correct
11 Correct 37 ms 188492 KB Output is correct
12 Correct 6 ms 188492 KB Output is correct
13 Correct 168 ms 188492 KB Output is correct
14 Correct 98 ms 188492 KB Output is correct
15 Correct 82 ms 188492 KB Output is correct
16 Correct 65 ms 188492 KB Output is correct
17 Correct 515 ms 188492 KB Output is correct
18 Correct 327 ms 188492 KB Output is correct
19 Correct 314 ms 188492 KB Output is correct
20 Correct 227 ms 188492 KB Output is correct
21 Correct 574 ms 188492 KB Output is correct
22 Correct 686 ms 188492 KB Output is correct
23 Correct 884 ms 188492 KB Output is correct
24 Correct 595 ms 188492 KB Output is correct
25 Correct 1487 ms 188492 KB Output is correct
26 Correct 1711 ms 188492 KB Output is correct
27 Execution timed out 2082 ms 204164 KB Time limit exceeded
28 Execution timed out 2082 ms 204164 KB Time limit exceeded
29 Execution timed out 2047 ms 204164 KB Time limit exceeded
30 Execution timed out 2084 ms 204164 KB Time limit exceeded
31 Execution timed out 2068 ms 204164 KB Time limit exceeded
32 Correct 1985 ms 209228 KB Output is correct