Submission #101447

#	Time	Username	Problem	Language	Result	Execution time	Memory
101447		jamielim	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	2178 ms	1049600 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

int h,w;
set<int> adj[16000000];
int vis[16000000];
int dist[16000000];
int cnt=0;
void dfs(int x){
    if(vis[x]==1)return;
    vis[x]=1;
    for(set<int>::iterator it=adj[x].begin();it!=adj[x].end();++it){
        int i=(*it);
        if(vis[i]==1)continue;
        if(dist[i]<dist[x]+1){
            dist[i]=dist[x]+1;
            dfs(i);
        }else if(vis[i]==0){
            dfs(i);
        }
    }
    vis[x]=2;
}

int main(){
    scanf("%d%d",&h,&w);
    char grid[h+5][w+5];
    for(int i=0;i<h;i++){
        scanf("%s",grid[i]);
    }
    queue<pair<int,int> > q;
    int com[h][w];
    memset(com,-1,sizeof(com));
    int c=0;
    int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(com[i][j]==-1){
                q.push(make_pair(i,j));
                com[i][j]=c;
                while(!q.empty()){
                    pair<int,int> cur=q.front();q.pop();
                    for(int k=0;k<4;k++){
                        int nx=cur.first+dx[k],ny=cur.second+dy[k];
                        if(nx<0||ny<0||nx>=h||ny>=w)continue;
                        if(grid[nx][ny]==grid[cur.first][cur.second]&&com[nx][ny]==-1){
                            com[nx][ny]=c;
                            q.push(make_pair(nx,ny));
                        }
                    }
                }
                c++;
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            for(int k=0;k<4;k++){
                int nx=i+dx[k],ny=j+dy[k];
                if(0<=nx&&nx<h&&0<=ny&&ny<w){
                    if(com[i][j]!=com[nx][ny]){
                        adj[com[i][j]].insert(com[nx][ny]);
                    }
                }
            }
        }
    }
    memset(dist,-1,sizeof(dist));
    dist[0]=0;
    dfs(0);
    int ans=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(grid[i][j]=='.'){
                ans=max(ans,dist[com[i][j]]);
            }
        }
    }
    printf("%d",ans);
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&h,&w);
     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",grid[i]);
         ~~~~~^~~~~~~~~~~~~~

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