QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#77784#4231. Rafting TripidontreallyknowAC ✓62ms48616kbC++174.2kb2023-02-15 16:32:512023-02-15 16:33:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-15 16:33:12]
  • 评测
  • 测评结果:AC
  • 用时:62ms
  • 内存:48616kb
  • [2023-02-15 16:32:51]
  • 提交

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'