oj.uz

Submission #136618

# Submission time Handle Problem Language Result Execution time Memory
136618 2019-07-25T20:28:30 Z Lawliet Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1668 ms 144940 KB 
#include <bits/stdc++.h>

#define MAX 4010

using namespace std;

int dx[] = {0 , 0 , 1 , -1};
int dy[] = {1 , -1 , 0 , 0};

int n, m;
int maxDist;

int dist[MAX][MAX];

bool marc[MAX][MAX];

char v[MAX][MAX];

deque<int> dq;

void add(int i, int j, int d, bool t = false)
{
	dist[i][j] = d;
	marc[i][j] = true;

	maxDist = max(maxDist , d);

	if(t)
	{
		dq.push_front(j);
		dq.push_front(i);
	}
	else
	{
		dq.push_back(i);
		dq.push_back(j);
	}
}

bool check(int i, int j)
{
	if(i <= 0 || j <= 0) return false;
	if(i > n || j > m) return false;
	if(v[i][j] == '.') return false;

	return !marc[i][j];
}

void BFS()
{
	add(1 , 1 , 1);

	while(!dq.empty())
	{
		int curX = dq.front(); dq.pop_front();
		int curY = dq.front(); dq.pop_front();

		for(int g = 0 ; g < 4 ; g++)
		{
			int dX = curX + dx[g];
			int dY = curY + dy[g];
			int d = dist[curX][curY];

			if(!check(dX , dY)) continue;

			if(v[dX][dY] != v[curX][curY]) add(dX , dY , d + 1);
			else add(dX , dY , d , true);
		}
	}
}

int main()
{
	scanf("%d %d",&n,&m);

	for(int g = 1 ; g <= n ; g++)
		for(int h = 1 ; h <= m ; h++)
			scanf(" %c",&v[g][h]);

	BFS();

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

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7416 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 22 ms 7132 KB Output is correct
5 Correct 11 ms 4088 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 4 ms 1528 KB Output is correct
10 Correct 10 ms 3576 KB Output is correct
11 Correct 8 ms 2936 KB Output is correct
12 Correct 14 ms 4344 KB Output is correct
13 Correct 12 ms 4088 KB Output is correct
14 Correct 11 ms 4088 KB Output is correct
15 Correct 31 ms 7288 KB Output is correct
16 Correct 35 ms 7416 KB Output is correct
17 Correct 30 ms 7160 KB Output is correct
18 Correct 22 ms 7160 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 45816 KB Output is correct
2 Correct 145 ms 20008 KB Output is correct
3 Correct 1137 ms 89340 KB Output is correct
4 Correct 299 ms 40184 KB Output is correct
5 Correct 679 ms 65272 KB Output is correct
6 Correct 1666 ms 123532 KB Output is correct
7 Correct 47 ms 47992 KB Output is correct
8 Correct 45 ms 45816 KB Output is correct
9 Correct 7 ms 764 KB Output is correct
10 Correct 4 ms 508 KB Output is correct
11 Correct 53 ms 47096 KB Output is correct
12 Correct 5 ms 2168 KB Output is correct
13 Correct 145 ms 19988 KB Output is correct
14 Correct 86 ms 14200 KB Output is correct
15 Correct 89 ms 17016 KB Output is correct
16 Correct 61 ms 7288 KB Output is correct
17 Correct 363 ms 36732 KB Output is correct
18 Correct 334 ms 43580 KB Output is correct
19 Correct 308 ms 40188 KB Output is correct
20 Correct 262 ms 32504 KB Output is correct
21 Correct 676 ms 64760 KB Output is correct
22 Correct 679 ms 65272 KB Output is correct
23 Correct 677 ms 53496 KB Output is correct
24 Correct 665 ms 62200 KB Output is correct
25 Correct 1303 ms 110248 KB Output is correct
26 Correct 1468 ms 144940 KB Output is correct
27 Correct 1605 ms 128756 KB Output is correct
28 Correct 1668 ms 123520 KB Output is correct
29 Correct 1658 ms 121256 KB Output is correct
30 Correct 1663 ms 125428 KB Output is correct
31 Correct 1140 ms 86268 KB Output is correct
32 Correct 1622 ms 126332 KB Output is correct