Submission #134833

#	Time	Username	Problem	Language	Result	Execution time	Memory
134833		CaroLinda	Tracks in the Snow (BOI13_tracks)	C++14	86.88 / 100	2113 ms	414708 KiB

tracks

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int inf = 0x3f3f3f3f ;
const int MAXN = 4010 ;

using namespace std ;

int n , m ;
int dx[4] = {1,0,-1,0} , dy[4] = {0,1,0,-1} ;
int d[MAXN][MAXN] ;
int adj[MAXN][MAXN][4] ;
char mat[MAXN][MAXN] ;
bool marc[MAXN][MAXN] ;
deque<pii> fila ;

bool valid(int x, int y) { return (x>=0 && x<n && y>=0 && y<m) ; }

int dijkstra01( pii S )
{
	lp(i,0,MAXN)
		lp(j,0,MAXN) d[i][j] = inf ;


	d[S.ff][S.ss] = 0 ;
	fila.push_front(S) ;


	while(true)
	{
		pii davez = mk(-1,-1) ;

		while(!fila.empty())
		{
			pii topo = fila.front();
			fila.pop_front() ;
			if(marc[topo.ff][topo.ss]) continue ;
			davez=topo ;
			break ;
		}
		if(davez == mk(-1,-1)) break ;

		marc[davez.ff][davez.ss] = true ;
		
		lp(k,0,4)
		{

			int x = davez.ff + dx[k] , y = davez.ss + dy[k] ;

			if( adj[davez.ff][davez.ss][k] == -1 || marc[x][y] ) continue ;

			if( adj[davez.ff][davez.ss][k] == 0 ) 
			{
				fila.push_front( mk(x,y) ) ;
				d[x][y] = d[davez.ff][davez.ss] ;
				continue ;
			}
			if( (d[davez.ff][davez.ss] + 1) >= d[x][y] ) continue ;

			fila.push_back(mk(x,y) ) ;
			d[x][y] = d[davez.ff][davez.ss] + 1 ;

		}

	}

	//Find largest distance
	int ans = -1 ;
	lp(i,0,n)
		lp(j,0,m)
			if(d[i][j] != inf)
				ans = max(ans, d[i][j]) ;

	return ans ;

}

int main()
{
	scanf("%d%d",&n,&m) ;
	lp(i,0,n)
		lp(j,0,m) scanf(" %c", &mat[i][j]) ;

	lp(i,0,n)
		lp(j,0,m)
			lp(k,0,4)
				{
					int x = i + dx[k] , y = j+dy[k] ;
					if(!valid(x,y) || mat[x][y] == '.') 
						{ adj[i][j][k] = -1 ; continue ; }

					adj[i][j][k] = (mat[x][y] == mat[i][j] ? 0 : 1) ;

				}

	int ans = dijkstra01( mk(0,0) ) ;

	printf("%d\n", ans+1 ) ;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m) ;
  ~~~~~^~~~~~~~~~~~~~
tracks.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   lp(j,0,m) scanf(" %c", &mat[i][j]) ;
             ~~~~~^~~~~~~~~~~~~~~~~~~

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