Submission #492122

#	Time	Username	Problem	Language	Result	Execution time	Memory
492122		ponkung	Tracks in the Snow (BOI13_tracks)	C++14	84.69 / 100	2099 ms	105720 KiB

tracks

#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 (stderr)

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 / 30
• Subtask 2: 54.6875 / 70