QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61406#4231. Rafting Trip2pal1rak#AC ✓53ms41464kbC++144.0kb2022-11-12 20:51:402022-11-12 20:51:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-12 20:51:40]
  • 评测
  • 测评结果:AC
  • 用时:53ms
  • 内存:41464kb
  • [2022-11-12 20:51:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
// mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());

const int cx[] = {-1, 1, 0, 0};
const int cy[] = {0, 0, -1, 1};

int N, M, ans, now;
char a[505][505];
int c[505][505];
pii nxt[505][505];
int wtr[505][505], vis[505][505], incyc[505][505];
vector<pii> redg[505][505], sgt[505][505];

void DFS(int x, int y) {
    if(incyc[x][y]) return;
    for(auto [a, b]: sgt[x][y]) {
        c[a][b]++;
        if(c[a][b] == 1)    now++;
    }
    ans = max(ans, now);
    for(auto [a, b]: redg[x][y])
        DFS(a, b);

    for(auto [a, b]: sgt[x][y]) {
        c[a][b]--;
        if(c[a][b] == 0)    now--;
    }
}

void solve_test() {
    scanf("%d%d\n", &N, &M);
    for(int i = 1; i <= N; i++) {
        scanf("%s", a[i] + 1);
    }

    for(int i = 0; i <= N + 1; i++) a[i][0] = a[i][M + 1] = '.';
    for(int j = 0; j <= M + 1; j++) a[0][j] = a[N + 1][j] = '.';

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) {
            if(a[i][j] == '#') {
                for(int k = 0; k < 4; k++)
                    sgt[i + cx[k]][j + cy[k]].push_back({i, j});
            } else if(a[i][j] == '<') {
                nxt[i][j] = {i, j - 1};
                redg[i][j - 1].push_back({i, j});
                wtr[i][j] = 1;
            } else if(a[i][j] == '>') {
                nxt[i][j] = {i, j + 1};
                redg[i][j + 1].push_back({i, j});
                wtr[i][j] = 1;
            } else if(a[i][j] == '^') {
                nxt[i][j] = {i - 1, j};
                redg[i - 1][j].push_back({i, j});
                wtr[i][j] = 1;
            } else if(a[i][j] == 'v') {
                nxt[i][j] = {i + 1, j};
                redg[i + 1][j].push_back({i, j});
                wtr[i][j] = 1;
            }
        }

    ans = 0; now = 0;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(wtr[i][j]) {
                int x, y;
                tie(x, y) = nxt[i][j];
                if(wtr[x][y])   continue;

                DFS(i, j);
            }

    int I = 0;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(wtr[i][j] && !vis[i][j]) {
                I++;
                int x = i, y = j;
                while(wtr[x][y] && !vis[x][y]) {
                    vis[x][y] = I;
                    tie(x, y) = nxt[x][y];
                }
                if(wtr[x][y] && vis[x][y] == I) {
                    int xx = x, yy = y;
                    vector<pii> cyc;
                    cyc.push_back({x, y});
                    tie(x, y) = nxt[x][y];
                    while(x != xx || y != yy) {
                        cyc.push_back({x, y});
                        tie(x, y) = nxt[x][y];
                    }

                    now = 0;
                    for(auto [x, y]: cyc) {
                        incyc[x][y] = 1;
                        for(auto [a, b]: sgt[x][y]) {
                            c[a][b]++;
                            if(c[a][b] == 1)    now++;
                        }
                    }

                    ans = max(ans, now);

                    for(auto [x, y]: cyc) {
                        for(auto [a, b]: redg[x][y])
                            DFS(a, b);
                    }

                    for(auto [x, y]: cyc) {
                        incyc[x][y] = 1;
                        for(auto [a, b]: sgt[x][y]) {
                            c[a][b]--;
                            if(c[a][b] == 0)    now--;
                        }
                    }
                }
            }

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

int main() {
#ifdef USEFOPEN
    freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
#endif

    cin.sync_with_stdio(false); cin.tie(0);

    int T = 1;
//    scanf("%d", &T);
    for(int t = 1; t <= T; t++) {
        //printf("Case #%d: ", t);
        solve_test();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 19004kb

input:

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

output:

4

result:

ok single line: '4'

Test #2:

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

input:

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

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 7ms
memory: 19832kb

input:

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

output:

5

result:

ok single line: '5'

Test #4:

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

input:

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

output:

2

result:

ok single line: '2'

Test #5:

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

input:

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

output:

2

result:

ok single line: '2'

Test #6:

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

input:

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

output:

6

result:

ok single line: '6'

Test #7:

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

input:

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

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 1ms
memory: 19008kb

input:

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

output:

4

result:

ok single line: '4'

Test #9:

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

input:

2 2
>.
.#

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 3ms
memory: 20548kb

input:

2 2
..
.v

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 45ms
memory: 36732kb

input:

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

output:

41195

result:

ok single line: '41195'

Test #12:

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

input:

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

output:

24926

result:

ok single line: '24926'

Test #13:

score: 0
Accepted
time: 22ms
memory: 33036kb

input:

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

output:

24924

result:

ok single line: '24924'

Test #14:

score: 0
Accepted
time: 45ms
memory: 32436kb

input:

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

output:

2056

result:

ok single line: '2056'

Test #15:

score: 0
Accepted
time: 34ms
memory: 31200kb

input:

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

output:

970

result:

ok single line: '970'

Test #16:

score: 0
Accepted
time: 49ms
memory: 31312kb

input:

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

output:

687

result:

ok single line: '687'

Test #17:

score: 0
Accepted
time: 49ms
memory: 31288kb

input:

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

output:

481

result:

ok single line: '481'

Test #18:

score: 0
Accepted
time: 33ms
memory: 27860kb

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: 48ms
memory: 29360kb

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: 42ms
memory: 29484kb

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: 42ms
memory: 28524kb

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: 33ms
memory: 34136kb

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: 28ms
memory: 28660kb

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: 21572kb

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: 6ms
memory: 20460kb

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: 26ms
memory: 36900kb

input:

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

output:

31270

result:

ok single line: '31270'

Test #27:

score: 0
Accepted
time: 28ms
memory: 41464kb

input:

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

output:

123584

result:

ok single line: '123584'

Test #28:

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

input:

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

output:

331

result:

ok single line: '331'

Test #29:

score: 0
Accepted
time: 18ms
memory: 33584kb

input:

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

output:

1234

result:

ok single line: '1234'

Test #30:

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

input:

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

output:

281

result:

ok single line: '281'

Test #31:

score: 0
Accepted
time: 53ms
memory: 33500kb

input:

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

output:

996

result:

ok single line: '996'