oj.uz

Submission #492122

# Submission time Handle Problem Language Result Execution time Memory
492122 2021-12-05T14:30:24 Z ponkung Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 105720 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,d[4005][4005],u,v,dx[]={1,-1,0,0},dy[]={0,0,1,-1},x,y,mx=-1;
char s[4005][4005];
priority_queue<tuple<int,int,int> > pq;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++)
        {
            d[i][j]=1e9;
        }
    }
    d[1][1]=1;
    pq.push({0,1,1});
    while(!pq.empty())
    {
        u=get<1>(pq.top());
        v=get<2>(pq.top());
        mx=max(mx,d[u][v]);
        pq.pop();
        for(int i=0;i<4;i++)
        {
            x=u+dx[i];
            y=v+dy[i];
            if(x>=1&&x<=n&&y>=1&&y<=m)
            {
                if(s[x][y]!='.')
                {
                    if(s[x][y]!=s[u][v])
                    {
                        if(d[u][v]+1<d[x][y])
                        {
                            d[x][y]=d[u][v]+1;
                            pq.push({-d[x][y],x,y});
                        }
                    }else
                    {
                        if(d[u][v]<d[x][y])
                        {
                            d[x][y]=d[u][v];
                            pq.push({-d[x][y],x,y});
                        }
                    }
                }
            }
        }
    }
    printf("%d\n",mx);
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf("%s",s[i]+1);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5452 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 30 ms 5468 KB Output is correct
5 Correct 5 ms 3020 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 5 ms 2508 KB Output is correct
11 Correct 8 ms 2252 KB Output is correct
12 Correct 17 ms 3140 KB Output is correct
13 Correct 5 ms 3020 KB Output is correct
14 Correct 5 ms 3020 KB Output is correct
15 Correct 36 ms 5584 KB Output is correct
16 Correct 50 ms 5668 KB Output is correct
17 Correct 21 ms 5316 KB Output is correct
18 Correct 31 ms 5508 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 30900 KB Output is correct
2 Correct 126 ms 17824 KB Output is correct
3 Correct 395 ms 80228 KB Output is correct
4 Correct 122 ms 31428 KB Output is correct
5 Correct 179 ms 60596 KB Output is correct
6 Execution timed out 2073 ms 104848 KB Time limit exceeded
7 Correct 15 ms 32204 KB Output is correct
8 Correct 15 ms 30908 KB Output is correct
9 Correct 5 ms 716 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 14 ms 31648 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 128 ms 17928 KB Output is correct
14 Correct 85 ms 11980 KB Output is correct
15 Correct 26 ms 13004 KB Output is correct
16 Correct 61 ms 6656 KB Output is correct
17 Correct 320 ms 33840 KB Output is correct
18 Correct 99 ms 33340 KB Output is correct
19 Correct 123 ms 31548 KB Output is correct
20 Correct 104 ms 29268 KB Output is correct
21 Correct 273 ms 62576 KB Output is correct
22 Correct 182 ms 60644 KB Output is correct
23 Correct 620 ms 51012 KB Output is correct
24 Correct 156 ms 62008 KB Output is correct
25 Correct 480 ms 80184 KB Output is correct
26 Correct 1558 ms 71256 KB Output is correct
27 Execution timed out 2074 ms 84284 KB Time limit exceeded
28 Execution timed out 2035 ms 105720 KB Time limit exceeded
29 Execution timed out 2096 ms 93380 KB Time limit exceeded
30 Execution timed out 2099 ms 91820 KB Time limit exceeded
31 Execution timed out 2099 ms 66176 KB Time limit exceeded
32 Execution timed out 2047 ms 82808 KB Time limit exceeded