oj.uz

답안 #63728

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 5880 KB Output is correct
2 Correct 4 ms 5880 KB Output is correct
3 Correct 3 ms 5880 KB Output is correct
4 Correct 23 ms 6252 KB Output is correct
5 Correct 8 ms 6252 KB Output is correct
6 Correct 3 ms 6252 KB Output is correct
7 Correct 3 ms 6252 KB Output is correct
8 Correct 3 ms 6252 KB Output is correct
9 Correct 3 ms 6252 KB Output is correct
10 Correct 8 ms 6252 KB Output is correct
11 Correct 7 ms 6252 KB Output is correct
12 Correct 12 ms 6252 KB Output is correct
13 Correct 7 ms 6252 KB Output is correct
14 Correct 7 ms 6252 KB Output is correct
15 Correct 27 ms 6252 KB Output is correct
16 Correct 29 ms 6252 KB Output is correct
17 Correct 22 ms 6252 KB Output is correct
18 Correct 19 ms 6380 KB Output is correct

Subtask #2
56.875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 31340 KB Output is correct
2 Correct 103 ms 31340 KB Output is correct
3 Correct 443 ms 94956 KB Output is correct
4 Correct 131 ms 94956 KB Output is correct
5 Correct 235 ms 94956 KB Output is correct
6 Execution timed out 2082 ms 184376 KB Time limit exceeded
7 Correct 27 ms 184376 KB Output is correct
8 Correct 31 ms 184376 KB Output is correct
9 Correct 5 ms 184376 KB Output is correct
10 Correct 3 ms 184376 KB Output is correct
11 Correct 27 ms 184376 KB Output is correct
12 Correct 4 ms 184376 KB Output is correct
13 Correct 89 ms 184376 KB Output is correct
14 Correct 50 ms 184376 KB Output is correct
15 Correct 40 ms 184376 KB Output is correct
16 Correct 46 ms 184376 KB Output is correct
17 Correct 271 ms 184376 KB Output is correct
18 Correct 155 ms 184376 KB Output is correct
19 Correct 119 ms 184376 KB Output is correct
20 Correct 99 ms 184376 KB Output is correct
21 Correct 334 ms 184376 KB Output is correct
22 Correct 210 ms 184376 KB Output is correct
23 Correct 620 ms 184376 KB Output is correct
24 Correct 296 ms 184376 KB Output is correct
25 Correct 697 ms 184376 KB Output is correct
26 Correct 1305 ms 184376 KB Output is correct
27 Execution timed out 2091 ms 209816 KB Time limit exceeded
28 Execution timed out 2074 ms 209816 KB Time limit exceeded
29 Execution timed out 2081 ms 209816 KB Time limit exceeded
30 Execution timed out 2099 ms 209816 KB Time limit exceeded
31 Execution timed out 2015 ms 209816 KB Time limit exceeded
32 Correct 1312 ms 209816 KB Output is correct