oj.uz

Submission #134833

# Submission time Handle Problem Language Result Execution time Memory
134833 2019-07-23T09:51:10 Z CaroLinda Tracks in the Snow (BOI13_tracks) C++14
86.875 / 100
 2000 ms 414708 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 73208 KB Output is correct
2 Correct 56 ms 63480 KB Output is correct
3 Correct 57 ms 63888 KB Output is correct
4 Correct 82 ms 71964 KB Output is correct
5 Correct 69 ms 68116 KB Output is correct
6 Correct 56 ms 63544 KB Output is correct
7 Correct 60 ms 63856 KB Output is correct
8 Correct 58 ms 63992 KB Output is correct
9 Correct 69 ms 64632 KB Output is correct
10 Correct 77 ms 67320 KB Output is correct
11 Correct 77 ms 66420 KB Output is correct
12 Correct 79 ms 68216 KB Output is correct
13 Correct 68 ms 68088 KB Output is correct
14 Correct 66 ms 68088 KB Output is correct
15 Correct 95 ms 73420 KB Output is correct
16 Correct 100 ms 73212 KB Output is correct
17 Correct 94 ms 72952 KB Output is correct
18 Correct 83 ms 71928 KB Output is correct

Subtask #2
56.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 109748 KB Output is correct
2 Correct 251 ms 104344 KB Output is correct
3 Correct 1602 ms 361524 KB Output is correct
4 Correct 513 ms 148056 KB Output is correct
5 Correct 949 ms 248528 KB Output is correct
6 Execution timed out 2037 ms 377804 KB Time limit exceeded
7 Correct 103 ms 111764 KB Output is correct
8 Correct 103 ms 109688 KB Output is correct
9 Correct 63 ms 64448 KB Output is correct
10 Correct 59 ms 63864 KB Output is correct
11 Correct 104 ms 110908 KB Output is correct
12 Correct 62 ms 65396 KB Output is correct
13 Correct 248 ms 104152 KB Output is correct
14 Correct 168 ms 89080 KB Output is correct
15 Correct 173 ms 91796 KB Output is correct
16 Correct 137 ms 78660 KB Output is correct
17 Correct 549 ms 154700 KB Output is correct
18 Correct 508 ms 153592 KB Output is correct
19 Correct 478 ms 148072 KB Output is correct
20 Correct 407 ms 141348 KB Output is correct
21 Correct 975 ms 254872 KB Output is correct
22 Correct 943 ms 248528 KB Output is correct
23 Correct 975 ms 221820 KB Output is correct
24 Correct 953 ms 251548 KB Output is correct
25 Correct 1960 ms 361356 KB Output is correct
26 Correct 1585 ms 408748 KB Output is correct
27 Execution timed out 2113 ms 414708 KB Time limit exceeded
28 Execution timed out 2075 ms 378932 KB Time limit exceeded
29 Execution timed out 2072 ms 377484 KB Time limit exceeded
30 Execution timed out 2081 ms 387812 KB Time limit exceeded
31 Correct 1722 ms 272300 KB Output is correct
32 Execution timed out 2019 ms 407456 KB Time limit exceeded