Submission #520163

#	Time	Username	Problem	Language	Result	Execution time	Memory
520163		krit3379	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1733 ms	759112 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define N 4005
#define K 6000000

struct A{
    int x,y;
};

int sz,a[N][N],di[4]={1,-1,0,0},dj[4]={0,0,1,-1};
char s[N][N];
bitset<N> vis[N];
bitset<K> ch;
queue<A> q;
set<int> se[K];

int main(){
    int n,m,i,j,k,x,y,num;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf(" %s",s[i]+1);
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(s[i][j]=='.'||vis[i][j])continue;
            q.push({i,j});
            vis[i][j]=true;
            a[i][j]=++sz;
            while(!q.empty()){
                x=q.front().x;
                y=q.front().y;
                q.pop();
                a[x][y]=sz;
                for(k=0;k<4;k++){
                    int X=x+di[k],Y=y+dj[k];
                    if(X>0&&X<=n&&Y>0&&Y<=m&&s[x][y]==s[X][Y]&&!vis[X][Y])q.push({X,Y}),vis[X][Y]=true;
                    else if(X>0&&X<=n&&Y>0&&Y<=m&&s[x][y]!=s[X][Y]&&s[X][Y]!='.'&&a[X][Y])se[a[x][y]].insert(a[X][Y]),se[a[X][Y]].insert(a[x][y]);
                }
            }
        }
    }
    q.push({a[1][1],1});
    ch[a[1][1]]=true;
    while(!q.empty()){
        x=q.front().x;
        y=q.front().y;
        q.pop();
        for(auto num:se[x])if(!ch[num])ch[num]=true,q.push({num,y+1});
    }
    printf("%d",y);
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:18:23: warning: unused variable 'num' [-Wunused-variable]
   18 |     int n,m,i,j,k,x,y,num;
      |                       ^~~
tracks.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
tracks.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf(" %s",s[i]+1);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70