QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#86566	#4231. Rafting Trip	cardinal_city^#	TL	7ms	12684kb	C++20	3.5kb	2023-03-10 08:47:19	2023-03-10 08:47:20

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-10 08:47:20]
评测

测评结果：TL
用时：7ms
内存：12684kb

查看

[2023-03-10 08:47:19]
提交

answer

#include <bits/stdc++.h>

using namespace std;

int bins[300000] = {};
int r,c; 
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
map<char, int> dir = {{'>', 0}, {'<', 1}, {'v', 2}, {'^', 3}, {'.', -1}, {'#', -1}};
int inv[300000] = {};
vector<int> cycidx(300000, -1);

vector<int> nxt(300000, -1000000);
vector<int> adjbins[300000];
vector<unordered_set<int>> cycbins;
int numcyc = 0;
int vis[300000] = {};
int ans = 0;

int currcyc = -1;
int sub = 0;

unordered_set<int> currbins;

int to_idx(int i, int j) {
    return (c+2) * i + j;
}

void dfs(int u) {
    if(vis[u] == 2) return;
    if(vis[u] == 1) {
        int v = nxt[u];
        vector<int> cyc = {u};
        while(v != u) {
            cyc.push_back(v);
            v = nxt[v];
        }
        unordered_set<int> cbins;
        for(auto x : cyc) {
            for(auto b : adjbins[x]) {
                cbins.insert(b);
            }
            cycidx[x] = numcyc;
        }
        cycbins.push_back(cbins);
        numcyc++;
        return;
    }
    vis[u] = 1;
    if(nxt[u] != -1000000) dfs(nxt[u]);
    vis[u] = 2;
    return;
}

void dfs2(int u) {
  //  cout << "U " << u << endl;
    if(cycidx[u] != -1) {
 //       cout << u << " " << cycidx[u] << " " << cycbins.size() << endl;
        currcyc = cycidx[u];
        for(int b : currbins) {
            if(cycbins[currcyc].count(b)) sub++;
        }
        return;
    }
    

    if(nxt[u] != -1000000) {
        for(int b : adjbins[u]) currbins.insert(b);
        dfs2(nxt[u]);
    }
}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> r >> c;
    char g[510][510] = {};
    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            cin >> g[i][j];
            if(g[i][j] == '#') bins[to_idx(i,j)] = 1;
        }
    }

    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            int d = dir[g[i][j]];
            int idx = to_idx(i,j);
            if(d >= 0) {
                int ni = i + dr[d];
                int nj = j + dc[d];
                int nidx = to_idx(ni, nj);
                inv[nidx]++;
                nxt[idx] = nidx;

                for(int k = 0; k < 4; k++) {
                    int ki = i + dr[k];
                    int kj = j + dc[k];
                    int kidx = to_idx(ki, kj);
                    if(bins[kidx]) adjbins[idx].push_back(kidx);
                }
            }
        }
    }

    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            int idx = to_idx(i,j);
            if(vis[idx] == 0 && nxt[idx] != -1000000) {
                dfs(idx);
            }
        }
    }

    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            int idx = to_idx(i,j);
            vis[idx] = 0;
        }
    }


    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            int idx = to_idx(i,j);
            currcyc = -1;
            sub = 0;
            if(inv[idx] == 0 && nxt[idx] != -1000000) {
                currbins.clear();
                dfs2(idx);
                int tot = currbins.size();
                if(currcyc != -1) {
                    ans += cycbins[currcyc].size() - sub;
                }
                ans = max(ans, tot);
            }

        }
    }

    for(auto x : cycbins) {
        ans = max(ans, (int) x.size());
    }

    cout << ans << endl;

    
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 12660kb

input:

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

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 1ms

memory: 12656kb

input:

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

output:

result:

ok single line: '2'

Test #3:

score: 0

Accepted

time: 7ms

memory: 12680kb

input:

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

output:

result:

ok single line: '5'

Test #4:

score: 0

Accepted

time: 2ms

memory: 12676kb

input:

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

output:

result:

ok single line: '2'

Test #5:

score: 0

Accepted

time: 5ms

memory: 12684kb

input:

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

output:

result:

ok single line: '2'

Test #6:

score: 0

Accepted

time: 3ms

memory: 12656kb

input:

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

output:

result:

ok single line: '6'

Test #7:

score: 0

Accepted

time: 2ms

memory: 12680kb

input:

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

output:

result:

ok single line: '3'

Test #8:

score: 0

Accepted

time: 1ms

memory: 12660kb

input:

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

output:

result:

ok single line: '4'

Test #9:

score: 0

Accepted

time: 4ms

memory: 12668kb

input:

2 2
>.
.#

output:

result:

ok single line: '0'

Test #10:

score: 0

Accepted

time: 4ms

memory: 12648kb

input:

2 2
..
.v

output:

result:

ok single line: '0'

Test #11:

score: -100

Time Limit Exceeded

input:

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