QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#375825#4231. Rafting Trip8BQube#WA 2ms9872kbC++205.2kb2024-04-03 16:16:332024-04-03 16:16:33

Judging History

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

  • [2024-04-03 16:16:33]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9872kb
  • [2024-04-03 16:16:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

string mp[505];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};
int mapping[100000], vis[505][505], tag[505][505], indeg[505][505], wei[505][505], dp[505][505];
pii bln[505][505];
int in[505][505], out[505][505], dft;
vector<pii> G[505][505];

void dfs(int x, int y, int p, int q) {
    in[x][y] = ++dft, bln[x][y] = pii(p, q);
    for (auto [a, b] : G[x][y])
        if (!in[a][b])
            dfs(a, b, p, q);
    out[x][y] = dft;
}

bool strict_ancestor(int x, int y, int a, int b) {
    return in[x][y] < in[a][b] && out[x][y] >= out[a][b];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    mapping['^'] = 0;
    mapping['v'] = 1;
    mapping['>'] = 2;
    mapping['<'] = 3;
    int r, c;
    cin >> r >> c;
    for (int i = 0; i < r; ++i)
        cin >> mp[i];

    auto river = [&](int a, int b) {
        if (a < 0 || a >= r || b < 0 || b >= c || mp[a][b] == '#' || mp[a][b] == '.') return false;
        return true;
    };
    
    auto sight = [&](int a, int b) {
        if (a < 0 || a >= r || b < 0 || b >= c) return false;
        return mp[a][b] == '#';
    };
    
    auto add = [&](int a, int b, int v) {
        if (!river(a, b)) return;
        indeg[a][b] += v;
    };

    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            if (river(i, j)) {
                int d = mapping[int(mp[i][j])];
                add(i + dx[d], j + dy[d], 1);
            }
    queue<pii> q;

    auto check = [&](int a, int b) {
        if (river(a, b) && !indeg[a][b])
            q.emplace(a, b);
    };

    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            check(i, j);

    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        int d = mapping[int(mp[i][j])];
        add(i + dx[d], j + dy[d], -1);
        check(i + dx[d], j + dy[d]);
    }

    vector<pii> root;

    auto add_edge = [&](int a, int b, int x, int y) {
        G[a][b].pb(pii(x, y));
    };

    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            if (river(i, j) && !indeg[i][j]) {
                bln[i][j] = pii(i, j);
                int d = mapping[int(mp[i][j])];
                if (river(i + dx[d], j + dy[d]) && !indeg[i + dx[d]][j + dy[d]])
                    add_edge(i + dx[d], j + dy[d], i, j);
                else
                    root.pb(pii(i, j));
            }
            else if (river(i, j) && indeg[i][j] && !vis[i][j]) {
                for (int x = i, y = j; !vis[x][y];) {
                    vis[x][y] = 1, bln[x][y] = pii(i, j);
                    int d = mapping[int(mp[x][y])];
                    x += dx[d], y += dy[d];
                }
            }

    for (auto [x, y] : root) {
        int d = mapping[int(mp[x][y])];
        int a = x, b = y;
        if (river(x + dx[d], y + dy[d]))
            tie(a, b) = bln[x + dx[d]][y + dy[d]];
        dfs(x, y, a, b);
    }

    int tp = 0;
    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            if (sight(i, j)) {
                vector<pii> riv;
                for (int d = 0; d < 4; ++d)
                    if (river(i + dx[d], j + dy[d]))
                        riv.pb(pii(i + dx[d], j + dy[d]));
                ++tp;
                for (auto [x, y] : riv)
                    if (indeg[x][y] && tag[bln[x][y].X][bln[x][y].Y] != tp) {
                        wei[bln[x][y].X][bln[x][y].Y] += 1;
                        tag[bln[x][y].X][bln[x][y].Y] = tp;
                    }
                for (auto [x, y] : riv) {
                    if (indeg[x][y]) continue;
                    int flag = (tag[bln[x][y].X][bln[x][y].Y] == tp);
                    for (auto [a, b] : riv) { 
                        if (indeg[a][b]) continue;
                        if (strict_ancestor(a, b, x, y))
                            flag = 1;
                    }
                    if (!flag)
                        wei[x][y] += 1; 
                }
            }

    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            indeg[i][j] = 0;

    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            if (river(i, j)) {
                int d = mapping[int(mp[i][j])];
                add(i + dx[d], j + dy[d], 1);
            }

    int ans = 0;

    auto add2 = [&](int a, int b, int v, int dpv) {
        if (!river(a, b)) return;
        dp[a][b] = max(dp[a][b], dpv);
        ans = max(ans, dp[a][b] + wei[bln[a][b].X][bln[a][b].Y]);
        indeg[a][b] += v;
    };

    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            check(i, j);

    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        dp[i][j] += wei[i][j];
        ans = max(ans, dp[i][j]);
        int d = mapping[int(mp[i][j])];
        add2(i + dx[d], j + dy[d], -1, dp[i][j]);
        check(i + dx[d], j + dy[d]);
    }

    cout << ans << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

4

result:

ok single line: '4'

Test #2:

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

input:

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

output:

2

result:

ok single line: '2'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 7788kb

input:

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

output:

0

result:

wrong answer 1st lines differ - expected: '5', found: '0'