Submission #134840

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134840	2019-07-23T09:59:44 Z	CaroLinda	Tracks in the Snow (BOI13_tracks)	C++14	89.0625 / 100	2000 ms	183344 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 = 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 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	7544 KB	Output is correct
2	Correct	2 ms	504 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	504 KB	Output is correct
7	Correct	3 ms	888 KB	Output is correct
8	Correct	3 ms	1148 KB	Output is correct
9	Correct	4 ms	1528 KB	Output is correct
10	Correct	11 ms	3576 KB	Output is correct
11	Correct	9 ms	3064 KB	Output is correct
12	Correct	18 ms	4216 KB	Output is correct
13	Correct	12 ms	4088 KB	Output is correct
14	Correct	12 ms	4088 KB	Output is correct
15	Correct	39 ms	7288 KB	Output is correct
16	Correct	44 ms	7544 KB	Output is correct
17	Correct	32 ms	7160 KB	Output is correct
18	Correct	28 ms	7288 KB	Output is correct

Subtask #2

59.0625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	45816 KB	Output is correct
2	Correct	172 ms	19480 KB	Output is correct
3	Correct	1211 ms	74624 KB	Output is correct
4	Correct	307 ms	37312 KB	Output is correct
5	Correct	695 ms	57628 KB	Output is correct
6	Execution timed out	2045 ms	127752 KB	Time limit exceeded
7	Correct	47 ms	47992 KB	Output is correct
8	Correct	46 ms	45816 KB	Output is correct
9	Correct	9 ms	760 KB	Output is correct
10	Correct	5 ms	504 KB	Output is correct
11	Correct	47 ms	47096 KB	Output is correct
12	Correct	5 ms	2168 KB	Output is correct
13	Correct	167 ms	18808 KB	Output is correct
14	Correct	100 ms	13432 KB	Output is correct
15	Correct	90 ms	16376 KB	Output is correct
16	Correct	80 ms	7032 KB	Output is correct
17	Correct	418 ms	33144 KB	Output is correct
18	Correct	347 ms	40056 KB	Output is correct
19	Correct	309 ms	36776 KB	Output is correct
20	Correct	282 ms	29340 KB	Output is correct
21	Correct	723 ms	55852 KB	Output is correct
22	Correct	703 ms	56544 KB	Output is correct
23	Correct	799 ms	46328 KB	Output is correct
24	Correct	652 ms	53368 KB	Output is correct
25	Correct	1356 ms	94732 KB	Output is correct
26	Correct	1546 ms	183344 KB	Output is correct
27	Execution timed out	2055 ms	148340 KB	Time limit exceeded
28	Execution timed out	2060 ms	126968 KB	Time limit exceeded
29	Execution timed out	2036 ms	125296 KB	Time limit exceeded
30	Execution timed out	2049 ms	136308 KB	Time limit exceeded
31	Correct	1750 ms	76572 KB	Output is correct
32	Correct	1928 ms	141172 KB	Output is correct