QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#65248#4231. Rafting TripSa3tElSefrAC ✓267ms328672kbC++234.4kb2022-11-29 06:31:452022-11-29 06:31:48

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-29 06:31:48]
  • 评测
  • 测评结果:AC
  • 用时:267ms
  • 内存:328672kb
  • [2022-11-29 06:31:45]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld double
typedef complex<ld> point;

const int N = 2000 + 5;

int n, m, cnt, freq[N][N], ans, nodeComp[N][N];
bool vis[N][N];
char grid[N][N];
vector<pair<int, int>> g[N][N], r[N][N];
stack<pair<int, int>> st;
vector<vector<pair<int, int>>> comps;
map<char, int> dir;
vector<int>compsG[N * N];

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

/*
dir['>'] = 0
dir['^'] = 2
dir['<'] = 1
dir['v'] = 3
*/

bool isRever(int i, int j) {
    return grid[i][j] != '.' && grid[i][j] != '#';
}

bool isValid(int i, int j) {
    return i < n && j < m && i >= 0 && j >= 0;
}

bool isRoot(int c) {
    if (comps[c].size() > 1) {
        return true;
    }
    auto u = comps[c].back();
    auto x = u.first;
    auto y = u.second;
    return r[x][y].empty();
}

void dfs(int x, int y, int rv) {
    vis[x][y] = true;
    auto &adj = rv ? r[x][y] : g[x][y];
    for (auto &i : adj) {
        auto n_x = i.first;
        auto n_y = i.second;
        if (!vis[n_x][n_y]) {
            dfs(n_x, n_y, rv);
        }
    }
    if (!rv) { 
        st.emplace(x, y);
    } else {
        comps.back().emplace_back(x, y);
        nodeComp[x][y] = comps.size() - 1;
        // cout << x << ' ' << y << ' ' << comps.size() - 1 << '\n';
    }
}

void kosaraju() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (isRever(i, j) && !vis[i][j]) {
                dfs(i, j, 0);
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    while (!st.empty()) {
        auto cur = st.top();
        st.pop();
        auto x = cur.first;
        auto y = cur.second;
        if (!vis[x][y]) {
            comps.push_back({});
            dfs(x, y, 1);
        }
    }
}

void add(pair<int, int> &u) {
    auto x = u.first;
    auto y = u.second;
    for (int i = 0; i < 4; ++i) {
        auto n_x = x + dx[i];
        auto n_y = y + dy[i];
        if (isValid(n_x, n_y) && grid[n_x][n_y] == '#') {
            if (!freq[n_x][n_y]++) {
                ++cnt;
            }
        }
    }
}

void rem(pair<int, int> &u) {
    auto x = u.first;
    auto y = u.second;
    for (int i = 0; i < 4; ++i) {
        auto n_x = x + dx[i];
        auto n_y = y + dy[i];
        if (isValid(n_x, n_y) && grid[n_x][n_y] == '#') {
            if (!--freq[n_x][n_y]) {
                --cnt;
            }
        }
    }
}

void solve(int c) {
    for (auto &node : comps[c]) {
        add(node);
    }
    // cout << "Component #" << c << ": " << cnt << '\n';
    ans = max(ans, cnt);
    for (auto &i : compsG[c]) {
        // cout << i << " x";
        solve(i);
    }
    for (auto &node : comps[c]) {
        rem(node);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    dir['>'] = 0;
    dir['^'] = 2;
    dir['<'] = 1;
    dir['v'] = 3;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (isRever(i, j)) {
                auto d = dir[grid[i][j]];
                auto n_x = i + dx[d];
                auto n_y = j + dy[d];
                if (isValid(n_x, n_y) && isRever(n_x, n_y)) {
                    g[n_x][n_y].emplace_back(i, j);
                    r[i][j].emplace_back(n_x, n_y);
                }
            }
        }
    }
    kosaraju();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (isRever(i, j)) {
                auto d = dir[grid[i][j]];
                auto n_x = i + dx[d];
                auto n_y = j + dy[d];
                if (isValid(n_x, n_y) && isRever(n_x, n_y)) {
                    auto c_1 = nodeComp[n_x][n_y];
                    auto c_2 = nodeComp[i][j];
                    // cout << c_1 << ' ' << c_2 << '\n';
                    if (c_1 != c_2) {
                        compsG[c_1].push_back(c_2);
                    }
                }
            }
        }
    }
    for (int c = 0; c < comps.size(); ++c) {
        if (isRoot(c)) {
            solve(c);
        }
    }
    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 102ms
memory: 290080kb

input:

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

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 109ms
memory: 289896kb

input:

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

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 118ms
memory: 290036kb

input:

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

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 148ms
memory: 290056kb

input:

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

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 121ms
memory: 289988kb

input:

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

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 120ms
memory: 289896kb

input:

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

output:

6

result:

ok single line: '6'

Test #7:

score: 0
Accepted
time: 126ms
memory: 289960kb

input:

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

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 128ms
memory: 289904kb

input:

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

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 104ms
memory: 289868kb

input:

2 2
>.
.#

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 116ms
memory: 290012kb

input:

2 2
..
.v

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 237ms
memory: 324932kb

input:

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

output:

41195

result:

ok single line: '41195'

Test #12:

score: 0
Accepted
time: 236ms
memory: 328672kb

input:

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

output:

24926

result:

ok single line: '24926'

Test #13:

score: 0
Accepted
time: 209ms
memory: 322024kb

input:

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

output:

24924

result:

ok single line: '24924'

Test #14:

score: 0
Accepted
time: 237ms
memory: 311040kb

input:

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

output:

2056

result:

ok single line: '2056'

Test #15:

score: 0
Accepted
time: 219ms
memory: 315544kb

input:

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

output:

970

result:

ok single line: '970'

Test #16:

score: 0
Accepted
time: 213ms
memory: 318404kb

input:

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

output:

687

result:

ok single line: '687'

Test #17:

score: 0
Accepted
time: 236ms
memory: 318632kb

input:

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

output:

481

result:

ok single line: '481'

Test #18:

score: 0
Accepted
time: 209ms
memory: 312616kb

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: 228ms
memory: 320512kb

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: 217ms
memory: 320532kb

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: 267ms
memory: 324996kb

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: 126ms
memory: 298180kb

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: 258ms
memory: 325324kb

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: 116ms
memory: 293832kb

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: 127ms
memory: 290124kb

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: 168ms
memory: 318996kb

input:

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

output:

31270

result:

ok single line: '31270'

Test #27:

score: 0
Accepted
time: 182ms
memory: 318996kb

input:

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

output:

123584

result:

ok single line: '123584'

Test #28:

score: 0
Accepted
time: 194ms
memory: 313232kb

input:

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

output:

331

result:

ok single line: '331'

Test #29:

score: 0
Accepted
time: 159ms
memory: 313244kb

input:

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

output:

1234

result:

ok single line: '1234'

Test #30:

score: 0
Accepted
time: 206ms
memory: 313140kb

input:

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

output:

281

result:

ok single line: '281'

Test #31:

score: 0
Accepted
time: 180ms
memory: 313256kb

input:

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

output:

996

result:

ok single line: '996'