QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#350477#4231. Rafting TripLaStataleBlueAC ✓32ms34700kbC++173.3kb2024-03-10 19:14:432024-03-10 19:14:43

Judging History

你现在查看的是最新测评结果

  • [2024-03-10 19:14:43]
  • 评测
  • 测评结果:AC
  • 用时:32ms
  • 内存:34700kb
  • [2024-03-10 19:14:43]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
constexpr int MAXR = 510;
constexpr int MAXN = MAXR * MAXR;

int R, C;
char terrain[MAXR][MAXR];
int to_node(short x, short y) { return x * (C + 2) + y; }
bool is_land(short x, short y) { return terrain[x][y] == '.' || terrain[x][y] == '#'; }

struct Coord
{
	const short x, y;
	Coord(int x, int y) : x(x), y(y) {}
	Coord operator+(const Coord &o) const { return {x + o.x, y + o.y}; }
	char get_terrain() const { return terrain[x][y]; }
	int to_node() const { return ::to_node(x, y); }
	bool is_land() const { return ::is_land(x, y); }
	Coord move_next() const
	{
		const char cell = terrain[x][y];
		if (cell == '^')
			return {x - 1, y};
		else if (cell == 'v')
			return {x + 1, y};
		else if (cell == '<')
			return {x, y - 1};
		else if (cell == '>')
			return {x, y + 1};
		return {x, y};
	}
};

int terr2node[MAXR][MAXR];
bool visited[MAXN];
bool visiting[MAXN];
bool loopnode[MAXN];
int dfs0(const Coord cell)
{
	if (cell.is_land())
		return -1;
	const int node = cell.to_node();
	if (visiting[node])
	{
		loopnode[node] = true;
		return node;
	}
	if (visited[node])
		return -1;
	visiting[node] = true;

	const int next = dfs0(cell.move_next());
	terr2node[cell.x][cell.y] = (next == -1) ? node : next;
	visiting[node] = false;
	visited[node] = true;
	if (node == next)
		return -1;
	return next;
}

vector<int> sons[MAXN];
vector<int> spots[MAXN];
int active_spots, ans;
int spots_counter[MAXN];
void dfs1(const int node)
{
	for (const int s : spots[node])
	{
		spots_counter[s]++;
		if (spots_counter[s] == 1)
			active_spots++;
	}
	ans = max(ans, active_spots);
	for (const int s : sons[node])
		dfs1(s);
	for (const int s : spots[node])
	{
		spots_counter[s]--;
		if (spots_counter[s] == 0)
			active_spots--;
	}
}

int main()
{
	scanf("%d %d", &R, &C);
	const int TERN = (R + 2) * (C + 2);
	for (int i = 1; i <= R; i++)
		scanf("%s", 1 + terrain[i]);
	fill(terrain[0], terrain[0] + C + 2, '.');
	fill(terrain[R + 1], terrain[R + 1] + C + 2, '.');
	for (int i = 1; i <= R; i++)
		terrain[i][0] = terrain[i][C + 1] = '.';

	for (int i = 0; i < R + 2; i++)
		for (int j = 0; j < C + 2; j++)
			if (is_land(i, j))
				terr2node[i][j] = TERN;
			else if (!visited[to_node(i, j)])
				dfs0({i, j});

	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			if (!is_land(i, j) && !loopnode[terr2node[i][j]])
			{
				const Coord next_coord = Coord{i, j}.move_next();
				const int next_node = terr2node[next_coord.x][next_coord.y];
				sons[next_node].push_back(to_node(i, j));
			}
	for (int i = 0; i < TERN; i++)
		if (loopnode[i])
			sons[TERN].push_back(i);

	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
		{
			const Coord c = {i, j};
			if (c.is_land())
				continue;
			for (const Coord d : {Coord{0, -1}, {0, 1}, {-1, 0}, {1, 0}})
				if ((c + d).get_terrain() == '#')
					spots[terr2node[c.x][c.y]].push_back((c + d).to_node());
		}
	for (int i = 0; i < TERN; i++)
		if (vector<int> &s = spots[i]; s.size() != 0)
		{
			sort(s.begin(), s.end());
			s.resize(unique(s.begin(), s.end()) - s.begin());
		}

	ans = 0;
	dfs1(TERN);
	printf("%d\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 16376kb

input:

5 6
v<<<#v
v#v<.>
>>v<<<
..v##^
#<<<.^

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 4ms
memory: 16796kb

input:

4 5
>v<<.
^<..#
#...#
.#>^#

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 4ms
memory: 16196kb

input:

4 6
>>v#>v
^#>>^v
^<<#v<
.#^<<#

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 0ms
memory: 16580kb

input:

6 6
^.>>>>
^.....
^....v
^....v
#....v
<<<<#v

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 18260kb

input:

6 7
^>>>>>v
^.....v
^.#^..v
^.#^<.v
^.....v
^<<<<<<

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 18136kb

input:

3 7
>v<<<<#
^<#####
#^<<<<<

output:

6

result:

ok single line: '6'

Test #7:

score: 0
Accepted
time: 4ms
memory: 18220kb

input:

3 5
><.v#
##.^#
...#.

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 4ms
memory: 16136kb

input:

7 3
###
#>#
###
...
###
#>.
###

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 0ms
memory: 16712kb

input:

2 2
>.
.#

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 0ms
memory: 18264kb

input:

2 2
..
.v

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 23ms
memory: 30716kb

input:

498 498
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...

output:

41195

result:

ok single line: '41195'

Test #12:

score: 0
Accepted
time: 25ms
memory: 33396kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

24926

result:

ok single line: '24926'

Test #13:

score: 0
Accepted
time: 15ms
memory: 30584kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

24924

result:

ok single line: '24924'

Test #14:

score: 0
Accepted
time: 15ms
memory: 21168kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

2056

result:

ok single line: '2056'

Test #15:

score: 0
Accepted
time: 24ms
memory: 23304kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

970

result:

ok single line: '970'

Test #16:

score: 0
Accepted
time: 32ms
memory: 25608kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

687

result:

ok single line: '687'

Test #17:

score: 0
Accepted
time: 29ms
memory: 25680kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

481

result:

ok single line: '481'

Test #18:

score: 0
Accepted
time: 23ms
memory: 23008kb

input:

500 500
.>^v.^<<^<<<<<<....><v#....^.#.^..#.^<<<<#..#.><v.v..>>^<<..###..^<v..#>>>#.....^>^#.##.#......#.....#v#.>v.v#..##.#.^>>>>>v..#.v<..^...^..^#....#..>v.#^<..^^v..^.....vv..v...#^.v>>v#.#.#..#.v.^v<<......^#<.v...v>>^^<^#..^^v.^..^..^...#.#.^...^^<<<...##...v.........^.^.....>>>>>#.....><<<^.....

output:

13

result:

ok single line: '13'

Test #19:

score: 0
Accepted
time: 23ms
memory: 24816kb

input:

500 499
<<<<<#v.^.^v>v<^^.^<>><>^.^v.><^.v^<.^^#..v#>>><<<v^<>>^>>v<<<<^^^^#<>v>^<>>>^>^<<<#^^#v<<<<<<<<v>#v<<v^v.v^<<^<##><<^^<>^<#^^.^#>v^<<^>>>>v^.^>>^<#^>v^#<<<<^><^#.v^>^.^^v<.#^<<<v.v^^^#^<<.>^^#vvv<<^..>#v<.^<<<>>v>>>^.#v#>>#^<<^v<.>^#^.><^<>#^<<^^^^<<<<.><..><<#^<<>>>>>>>^^<>#>v<><#^^><v<><>...

output:

13

result:

ok single line: '13'

Test #20:

score: 0
Accepted
time: 31ms
memory: 24816kb

input:

499 500
v^^.#<^^^..>^.v^<^<<v>^<<^>^#^^v^.>vv<v.>v.^<<<<<.v.^>>v<^#v##<^<<<vv^^^^^.>^v...#>v#.#v^^>^<<>v>>v#<><v>#vv<>>v^.>v<^<v>^#>^<<<>^>v^^..vv<<<v#<<.^^<<.v^<>^<<v^<><<vvv#<<v.##^><vv^>^>^v^##>v>>>^^v.#>^.^.^#.v<<<<^#.^^<^^#.>v.#^<^^^..v<>v<.#.^.v#v^..#>v<vv<<<<<>#v^v.#>#..><>>^...^.#><^>>>>>>>>...

output:

12

result:

ok single line: '12'

Test #21:

score: 0
Accepted
time: 27ms
memory: 24784kb

input:

500 500
^v>>v>v<>>>^#>v<^<>>>>v<<<^v.>^><.v>v<>^>vv^v>>><.>^v>>#^<<<>^<vv^^>>>v<v.^^v>v<vv<^>vv^<<vv<^^^^>>^^<^>>^^>>#<v^>v>>^<v<#<<vv<<<<<<<<<<<<<<<<<<^^v>^^<^^^v^<<#><<><>^>^>>>v<>>v><<^^<v^v<>>>^<v>>^vv>>v>>>v>v.v.v<v>#^<<<<<<<<<<.>v>^<<<<><^v<>v#<.^>^>^vv.v<>^v#<##^v^>^#v<v<<<<>>>#^>v>>>>>v^^>>^...

output:

11

result:

ok single line: '11'

Test #22:

score: 0
Accepted
time: 6ms
memory: 19900kb

input:

500 500
######<##############^#####>########v##########v###############################<######<#####>######v########################v####v##########>######v####<##########^#<##################<#####<########v#######<^####^v#####################^v####>#########^###########.v####<##########v##########...

output:

10

result:

ok single line: '10'

Test #23:

score: 0
Accepted
time: 30ms
memory: 24776kb

input:

500 500
<^^<^>><##<v>^>>#<^>v<^v<^^^<<><^^^<^v<^<^^^v#v<<<vv<vv^>>>>>>><vv<<<<>vv^^<^^>><<^<^>^<>^><v>^>^vv>^>^><<^v>^<<>vvv><>>>>>^vv>>#<>>>^^<v<<<^>v^^^<#<<^v^<<>>>>><##^>>#<<<<<<<<^><<<<<<^v^vv.^><>v^^v<v^>vv#^<<<^<<>#>^>>v>^>^^<^>>>^<v<<<v#v^>^^^<^<>^^<vv<<<#>v<v<^v^#^^>>>>^v^^<<>>#>>v<<<<v^<vv>...

output:

14

result:

ok single line: '14'

Test #24:

score: 0
Accepted
time: 2ms
memory: 18392kb

input:

500 2
<v
.#
.#
vv
#<
v^
<>
<^
v.
#>
>#
v^
#<
^#
#<
>v
<>
^.
#.
<<
#<
>>
>#
>>
#<
#v
^#
<<
#^
#v
#^
^.
^#
v#
##
#>
<<
#^
v^
<v
^#
^>
>#
.v
#^
<#
##
.v
>#
##
^#
^<
^^
<#
.>
<^
v<
><
<v
#v
##
#>
#>
##
##
^#
v>
><
.^
v#
#^
v>
<v
##
##
#>
>v
#v
><
.#
#.
^#
#.
>#
v<
>#
#<
<^
^#
#.
<>
#^
.v
##
.v
.v
.#
>>
...

output:

6

result:

ok single line: '6'

Test #25:

score: 0
Accepted
time: 4ms
memory: 18172kb

input:

2 500
v##v#>>>>^>>#.##<<.>>^#.v^>^^>##^>^^##v^^#.^<#<###<##v#^>^^.v>v#<^<<##^#^.#<##>#>>#v#>^#vv.^v#>v.####.>#.>>v#<.>#^..#<v##>>>^#v###^<#^#<#^^#>v^>###>>>><#^#v>v.v<^.#v.v##<.####<<<^#>^#^#<#>v#>#>^#>##.>>>^^<##<^^<v<...#v#.#<>>>>#.##.v#<.##.^#<^>#<<vv^>^#^..#<^##^^#<<##.vv<v^#<><.#<<.^^##^.#<v.##...

output:

5

result:

ok single line: '5'

Test #26:

score: 0
Accepted
time: 12ms
memory: 32496kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

31270

result:

ok single line: '31270'

Test #27:

score: 0
Accepted
time: 21ms
memory: 34700kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

123584

result:

ok single line: '123584'

Test #28:

score: 0
Accepted
time: 14ms
memory: 24716kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

331

result:

ok single line: '331'

Test #29:

score: 0
Accepted
time: 21ms
memory: 26872kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

1234

result:

ok single line: '1234'

Test #30:

score: 0
Accepted
time: 12ms
memory: 24724kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

281

result:

ok single line: '281'

Test #31:

score: 0
Accepted
time: 19ms
memory: 26744kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

996

result:

ok single line: '996'