QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#350477 | #4231. Rafting Trip | LaStataleBlue | AC ✓ | 32ms | 34700kb | C++17 | 3.3kb | 2024-03-10 19:14:43 | 2024-03-10 19:14:43 |
Judging History
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'