QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#77784 | #4231. Rafting Trip | idontreallyknow | AC ✓ | 62ms | 48616kb | C++17 | 4.2kb | 2023-02-15 16:32:51 | 2023-02-15 16:33:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fi first
#define se second
template<typename... T>
void dbg(T... t) {initializer_list<int>{(cerr << t << ' ', 0)...}; cerr << '\n';}
const int mx = 505;
int r,c,vis[mx][mx], col[mx][mx], cyc[mx][mx];
string g[mx];
pii nxt(pii x, char c) {
if (c == '<') x.se--;
else if (c == '>') x.se++;
else if (c == '^') x.fi--;
else if (c == 'v') x.fi++;
else {
assert(false);
}
return x;
}
bool ok(int x, int y) {
return x >= 0 && x < r && y >= 0 && y < c;
}
bool ok(pii x) {
return x.fi >= 0 && x.fi < r && x.se >= 0 && x.se < c;
}
int conv(pii p) {
return c*p.fi+p.se;
}
pii conv(int x) {
return {x/c, x%c};
}
vector<int> radj[mx*mx];
int ans = 0;
set<pii> spots;
vector<int> dx = {1,0,-1,0};
vector<int> dy = {0,1,0,-1};
void dfs(int sq) { // assert invariants?
pii pos = conv(sq);
set<pii> ins;
for (int q = 0; q < 4; q++) {
int nx = pos.fi+dx[q], ny = pos.se+dy[q];
if (ok(nx,ny) && g[nx][ny] == '#') {
if (spots.find({nx,ny}) == spots.end()) {
ins.insert({nx,ny});
spots.insert({nx,ny});
}
}
}
ans = max<int>(ans, spots.size());
for (auto rpos : radj[sq]) {
dfs(rpos);
}
for (auto p : ins) {
spots.erase(p);
}
}
int main() {
cin >> r >> c;
for (int q = 0; q < r; q++) cin >> g[q];
vector<pii> term;
vector<vector<pii>> cycles;
for (int q = 0; q < r; q++) {
for (int w = 0; w < c; w++) {
if (g[q][w] == '#' || g[q][w] == '.' || col[q][w]) continue;
pii cur{q,w};
while (col[cur.fi][cur.se] != 1) {
col[cur.fi][cur.se] = 1;
pii nc = nxt(cur, g[cur.fi][cur.se]);
if (!ok(nc) || g[nc.fi][nc.se] == '#' || g[nc.fi][nc.se] == '.') {
term.push_back(cur);
break;
} else if (col[nc.fi][nc.se] == 2) {
break;
} else if (col[nc.fi][nc.se] == 1) {
pii tmp = cur;
cycles.emplace_back();
while (col[tmp.fi][tmp.se] != 2) {
cycles.back().push_back(tmp);
col[tmp.fi][tmp.se] = 2;
cyc[tmp.fi][tmp.se] = 1;
tmp = nxt(tmp,g[tmp.fi][tmp.se]);
}
break;
} else {
cur = nc;
}
}
cur = pii{q,w};
while (col[cur.fi][cur.se] != 2) {
col[cur.fi][cur.se] = 2;
pii nc = nxt(cur, g[cur.fi][cur.se]);
if (!ok(nc) || g[nc.fi][nc.se] == '#' || g[nc.fi][nc.se] == '.') {
break;
} else if (col[nc.fi][nc.se] == 2) {
break;
} else {
assert(col[nc.fi][nc.se] == 1);
cur = nc;
}
}
}
}
for (int q = 0; q < r; q++) {
for (int w = 0; w < c; w++) {
if (g[q][w] != '#' && g[q][w] != '.') {
pii nc = nxt({q,w},g[q][w]);
if (ok(nc) && g[nc.fi][nc.se] != '#' && g[nc.fi][nc.se] != '.') {
radj[conv(nc)].push_back(conv({q,w}));
}
}
}
}
for (auto p : term) {
dfs(conv(p));
}
for (const auto& cycle : cycles) {
spots.clear();
vector<int> roots;
for (auto pos : cycle) {
for (int e = 0; e < 4; e++) {
int nx = pos.fi+dx[e], ny = pos.se+dy[e];
if (ok(nx,ny) && g[nx][ny] == '#') spots.insert({nx,ny});
}
for (auto rpos : radj[conv(pos)]) {
pii place = conv(rpos);
if (!cyc[place.fi][place.se]) roots.push_back(rpos);
}
}
ans = max<int>(ans, spots.size());
for (auto r : roots) {
dfs(r);
}
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10444kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 9708kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 4ms
memory: 10784kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 0ms
memory: 9576kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 11120kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 4ms
memory: 10708kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 0ms
memory: 10732kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 3ms
memory: 10156kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 0ms
memory: 11252kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 1ms
memory: 11416kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 60ms
memory: 34180kb
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
41195
result:
ok single line: '41195'
Test #12:
score: 0
Accepted
time: 52ms
memory: 39600kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24926
result:
ok single line: '24926'
Test #13:
score: 0
Accepted
time: 49ms
memory: 28660kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24924
result:
ok single line: '24924'
Test #14:
score: 0
Accepted
time: 37ms
memory: 17624kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
2056
result:
ok single line: '2056'
Test #15:
score: 0
Accepted
time: 55ms
memory: 17248kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
970
result:
ok single line: '970'
Test #16:
score: 0
Accepted
time: 61ms
memory: 16460kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
687
result:
ok single line: '687'
Test #17:
score: 0
Accepted
time: 52ms
memory: 16116kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
481
result:
ok single line: '481'
Test #18:
score: 0
Accepted
time: 33ms
memory: 15344kb
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: 46ms
memory: 16856kb
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: 41ms
memory: 16832kb
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: 49ms
memory: 17392kb
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: 13ms
memory: 12092kb
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: 58ms
memory: 17488kb
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: 11340kb
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: 10488kb
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: 35ms
memory: 40236kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
31270
result:
ok single line: '31270'
Test #27:
score: 0
Accepted
time: 61ms
memory: 48616kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
123584
result:
ok single line: '123584'
Test #28:
score: 0
Accepted
time: 40ms
memory: 15996kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
331
result:
ok single line: '331'
Test #29:
score: 0
Accepted
time: 53ms
memory: 15724kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
1234
result:
ok single line: '1234'
Test #30:
score: 0
Accepted
time: 25ms
memory: 15908kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
281
result:
ok single line: '281'
Test #31:
score: 0
Accepted
time: 62ms
memory: 15920kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
996
result:
ok single line: '996'