Submission #595052

#TimeUsernameProblemLanguageResultExecution timeMemory
595052ShivanshJTracks in the Snow (BOI13_tracks)C++17
100 / 100
923 ms258256 KiB
#include <bits/stdc++.h> //#define int long long using namespace std; const int MAX=4e3+5; const int INF=1e18; const int MOD=1e9+7; const int MAXL=32; int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; int g[MAX][MAX][2],h,w; // {T,R,B,L} , vertex-info (4) bool chk(int x,int y) { return (x>=0 && y>=0 && x<h && y<w && g[x][y][0]!=-1); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //cout<<setprecision(6)<<fixed; //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin>>h>>w; for(int i=0;i<h;i++) { for(int j=0;j<w;j++) { char s; cin>>s; if(s=='R') { g[i][j][0]=0; } else if(s=='F') { g[i][j][0]=1; } else { g[i][j][0]=-1; } } } deque<tuple<int,int,int>>dq; //{x,y,dist} dq.push_front({0,0,1}); int ans=1; while(!dq.empty()) { tuple<int,int,int>curr=dq.front(); dq.pop_front(); int x=get<0>(curr),y=get<1>(curr),d=get<2>(curr); if(g[x][y][1]>0) { continue; } g[x][y][1]=d; ans=max(ans,d); for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(!chk(nx,ny) || g[nx][ny][1]>0) { continue; } if(g[x][y][0]==g[nx][ny][0]) { dq.push_front({nx,ny,d}); } else { dq.push_back({nx,ny,d+1}); } } } cout<<ans; return 0; }

Compilation message (stderr)

tracks.cpp:5:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    5 | const int INF=1e18;
      |               ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...