Submission #134842

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134842	2019-07-23T10:00:52 Z	CaroLinda	Tracks in the Snow (BOI13_tracks)	C++14	89.0625 / 100	2000 ms	185552 KB

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 = 4123 ;

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 main()
{
	scanf("%d%d",&n,&m) ;
	lp(i,0,n)
		lp(j,0,m) 
			scanf(" %c", &mat[i][j]) ;

	fila.push_front(mk(0,0)) ;
	d[0][0] = 1 ;
	int ans = 1 ;

	while(!fila.empty())
	{
		pii p = fila.front() ;

		fila.pop_front() ;

		marc[p.ff][p.ss] = true ;

		lp(i,0,4)
		{
			int x = p.ff+dx[i] , y = p.ss+dy[i] ;
			
			if(!valid(x,y) || mat[x][y] =='.' || marc[x][y]) continue ;

			d[x][y] = d[p.ff][p.ss] ;

			if(mat[x][y] == mat[p.ff][p.ss])
				fila.push_front(mk(x,y)) ;

			else fila.push_back(mk(x,y)) , d[x][y] ++ ;

			ans = max(ans, d[x][y]) ;
		}
	}

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

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:28: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:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &mat[i][j]) ;
    ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	7288 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	3 ms	888 KB	Output is correct
4	Correct	28 ms	7288 KB	Output is correct
5	Correct	12 ms	4088 KB	Output is correct
6	Correct	2 ms	632 KB	Output is correct
7	Correct	3 ms	1016 KB	Output is correct
8	Correct	3 ms	1144 KB	Output is correct
9	Correct	4 ms	1528 KB	Output is correct
10	Correct	10 ms	3448 KB	Output is correct
11	Correct	10 ms	3064 KB	Output is correct
12	Correct	18 ms	4216 KB	Output is correct
13	Correct	11 ms	4088 KB	Output is correct
14	Correct	12 ms	4088 KB	Output is correct
15	Correct	39 ms	7160 KB	Output is correct
16	Correct	44 ms	7416 KB	Output is correct
17	Correct	31 ms	7032 KB	Output is correct
18	Correct	28 ms	7416 KB	Output is correct

Subtask #2

59.0625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	46584 KB	Output is correct
2	Correct	167 ms	18660 KB	Output is correct
3	Correct	1223 ms	75060 KB	Output is correct
4	Correct	308 ms	36984 KB	Output is correct
5	Correct	687 ms	57336 KB	Output is correct
6	Execution timed out	2076 ms	129376 KB	Time limit exceeded
7	Correct	49 ms	48632 KB	Output is correct
8	Correct	47 ms	46584 KB	Output is correct
9	Correct	8 ms	760 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	57 ms	47736 KB	Output is correct
12	Correct	5 ms	2168 KB	Output is correct
13	Correct	181 ms	18788 KB	Output is correct
14	Correct	100 ms	13304 KB	Output is correct
15	Correct	90 ms	16252 KB	Output is correct
16	Correct	76 ms	6876 KB	Output is correct
17	Correct	429 ms	33528 KB	Output is correct
18	Correct	338 ms	40184 KB	Output is correct
19	Correct	315 ms	36956 KB	Output is correct
20	Correct	281 ms	29560 KB	Output is correct
21	Correct	726 ms	56260 KB	Output is correct
22	Correct	690 ms	57392 KB	Output is correct
23	Correct	793 ms	46672 KB	Output is correct
24	Correct	650 ms	53924 KB	Output is correct
25	Correct	1372 ms	97244 KB	Output is correct
26	Correct	1516 ms	185552 KB	Output is correct
27	Execution timed out	2061 ms	150924 KB	Time limit exceeded
28	Execution timed out	2055 ms	129336 KB	Time limit exceeded
29	Execution timed out	2055 ms	127852 KB	Time limit exceeded
30	Execution timed out	2067 ms	138652 KB	Time limit exceeded
31	Correct	1765 ms	78836 KB	Output is correct
32	Correct	1924 ms	144004 KB	Output is correct