QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100368#4231. Rafting TripBeevoWA 13ms32768kbC++232.9kb2023-04-25 18:26:182023-04-25 18:26:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 18:26:19]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:32768kb
  • [2023-04-25 18:26:18]
  • 提交

answer

#include <bits/stdc++.h>

#define el '\n'

typedef long long ll;
typedef long double ld;

#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 500 * 500 + 5;

int r, c;
stack<int> st;
int id, mx = 0;
vector<int> G[N];
map<int, int> freq;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
set<int> g[N], windows[N];
vector<vector<int>> comps;
int tin[N], lowLink[N], state[N], root[N], in[N];

bool valid(int x, int y) {
    return x >= 0 && x < r && y >= 0 && y < c;
}

void tarjan(int u)
{
    st.push(u);
    state[u] = 1;
    tin[u] = lowLink[u] = ++id;

    for(auto &v: G[u])
    {
        if(!state[v])
        {
            tarjan(v);
            lowLink[u] = min(lowLink[u], lowLink[v]);
        }
        else if(state[v] == 1)
            lowLink[u] = min(lowLink[u], tin[v]);
    }

    if(tin[u] == lowLink[u])
    {
        while(st.top() != u) {
            state[st.top()] = 2, st.pop(), root[st.top()] = u;

            for (auto &i: windows[st.top()])
                windows[u].insert(i);
        }
        state[st.top()] = 2, st.pop(), root[u] = u;
    }
}

void dfs(int u) {
    for (auto &i: windows[u])
        freq[i]++;

    mx = max(mx, (int)freq.size());

    for (auto &v: g[u])
        dfs(v);

    for (auto &i: windows[u]) {
        freq[i]--;

        if (!freq[i])
            freq.erase(i);
    }
}

void testCase() {
    cin >> r >> c;

    char a[r][c];
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++)
            cin >> a[i][j];
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (a[i][j] == '#' || a[i][j] == '.')
                continue;

            if (a[i][j] == '>' && j + 1 < c)
                G[i * c + j + 1].push_back(i * c + j);

            if (a[i][j] == '<' && j - 1 >= 0)
                G[i * c + j - 1].push_back(i * c + j);

            if (a[i][j] == 'v' && i + 1 < r)
                G[(i + 1) * c + j].push_back(i * c + j);

            if (a[i][j] == '^' && i - 1 >= 0)
                G[(i - 1) * c + j].push_back(i * c + j);

            for (int k = 0; k < 4; k++) {
                if (valid(i + dx[k], j + dy[k]) && a[i + dx[k]][j + dy[k]] == '#')
                    windows[i * c + j].insert((i + dx[k]) * c + j + dy[k]);
            }
        }
    }

    for (int i = 0; i < r * c; i++) {
        if (state[i] != 2)
            tarjan(i);
    }

    for (int i = 0; i < r * c; i++) {
        for (auto &j: G[i]) {
            if (root[i] != root[j]) {
                in[root[j]]++;
                g[root[i]].insert(root[j]);
            }
        }
    }

    for (int i = 0; i < r * c; i++) {
        if (root[i] == i && !in[i])
            dfs(i);
    }

    cout << mx;
}

signed main() {
    Beevo

    int t = 1;
//    cin >> t;

    while (t--)
        testCase();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 32748kb

input:

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

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 5ms
memory: 32644kb

input:

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

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 9ms
memory: 32752kb

input:

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

output:

5

result:

ok single line: '5'

Test #4:

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

input:

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

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 4ms
memory: 32768kb

input:

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

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 13ms
memory: 32676kb

input:

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

output:

6

result:

ok single line: '6'

Test #7:

score: -100
Wrong Answer
time: 4ms
memory: 32676kb

input:

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

output:

0

result:

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