QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#793533	#4231. Rafting Trip	lukamosiashvili^#	RE	4ms	20964kb	C++17	3.1kb	2024-11-29 20:56:02	2024-11-29 20:56:02

Judging History

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

[2024-11-29 20:56:02]
评测

测评结果：RE
用时：4ms
内存：20964kb

查看

[2024-11-29 20:56:02]
提交

answer

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

char ch[509][509], id[509][509];
vector <int> v[250009], adj[250009];
int cudi[250009], msh[250009];
int been[250009], cik[250009];
int bo[250009], comp;
int cnt[250009];
int ans, PAS;

void dfs(int i){
    bo[i] = 1;
    if(cik[i] != comp || cik[i] == i){
        for(auto x:v[i]){
            if(cnt[x] == 0) ans++;
            cnt[x]++;
        }
    }

    PAS = max(PAS, ans);

    //cout << i << " " << ans << "\n";

    for(auto x:adj[i]){
        if(bo[x] == 1) continue;
        dfs(x);
    }

    if(cik[i] != comp || cik[i] == i){
        for(auto x:v[i]){
            if(cnt[x] == 1) ans--;
            cnt[x]--;
        }
    }
}

char yle[250009];

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        for(int j = 1; j <= m; j++){
            ch[i][j] = s[j - 1];
            id[i][j] = (i - 1) * m + j;
            yle[id[i][j]] = ch[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int ii, jj;
            if(ch[i][j] == '<'){
                ii = i; jj = j - 1;
                msh[id[i][j]] = id[ii][jj];
            }

            if(ch[i][j] == '^'){
                ii = i - 1; jj = j;
                msh[id[i][j]] = id[ii][jj];
            }

            if(ch[i][j] == '>'){
                ii = i; jj = j + 1;
                msh[id[i][j]] = id[ii][jj];
            }

            if(ch[i][j] == 'v'){
                ii = i + 1; jj = j;
                msh[id[i][j]] = id[ii][jj];
            }

            if(ch[i][j] == '#'){
                v[id[i - 1][j]].push_back(id[i][j]);
                v[id[i + 1][j]].push_back(id[i][j]);
                v[id[i][j - 1]].push_back(id[i][j]);
                v[id[i][j + 1]].push_back(id[i][j]);
            }

            if(ch[i][j] == '#' || ch[i][j] == '.')
                cudi[id[i][j]] = 1;
        }
    }

    for(int i = 1; i <= n * m; i++){
        if(yle[msh[i]] == '#' || yle[msh[i]] == '.') msh[i] = 0;
    }

    for(int i = 1; i <= n * m; i++){
        if(cudi[i]) continue;
        if(msh[i] != 0) adj[msh[i]].push_back(i);

        int c = i;
        while(c && !been[c]){
            been[c] = i;
            int e = c;
            c = msh[c];
            if(been[c] == i){
                int d = c;
                int xo = d;
                cik[d] = xo;
                while(d != e){
                    d = msh[d];
                    cik[d] = xo;
                    for(auto x: v[d]){
                        v[xo].push_back(x);
                    }
                }
                break;
            }

            if(c == 0){
                cik[e] = e;
            }
        }
    }

    for(int i = 1; i <= n * m; i++){
        if(cik[i] != i) continue;
        if(bo[i]) continue;
        comp = i;
        ans = 0;
        dfs(i);
    }

    cout << PAS;

    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 18108kb

input:

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

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 0ms

memory: 17912kb

input:

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

output:

result:

ok single line: '2'

Test #3:

score: 0

Accepted

time: 4ms

memory: 20964kb

input:

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

output:

result:

ok single line: '5'

Test #4:

score: 0

Accepted

time: 3ms

memory: 18008kb

input:

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

output:

result:

ok single line: '2'

Test #5:

score: 0

Accepted

time: 0ms

memory: 18020kb

input:

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

output:

result:

ok single line: '2'

Test #6:

score: 0

Accepted

time: 4ms

memory: 20864kb

input:

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

output:

result:

ok single line: '6'

Test #7:

score: 0

Accepted

time: 3ms

memory: 18452kb

input:

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

output:

result:

ok single line: '3'

Test #8:

score: 0

Accepted

time: 0ms

memory: 17376kb

input:

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

output:

result:

ok single line: '4'

Test #9:

score: 0

Accepted

time: 3ms

memory: 17560kb

input:

2 2
>.
.#

output:

result:

ok single line: '0'

Test #10:

score: 0

Accepted

time: 3ms

memory: 20352kb

input:

2 2
..
.v

output:

result:

ok single line: '0'

Test #11:

score: -100

Runtime Error

input:

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