QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33791#4231. Rafting TripBalintR#WA 24ms29348kbC++3.8kb2022-06-05 08:23:582022-06-05 08:23:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-05 08:23:58]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:29348kb
  • [2022-06-05 08:23:58]
  • 提交

answer

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

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << arr[_i]; cerr << endl;}

const pii MOVES[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int MW = 512;
const int MN = MW*MW;
int n, h, w;
string grid[MW];

int getCell(int i, int j){
    if(i < 0 || i >= h || j < 0 || j >= w || grid[i][j] == '.' || grid[i][j] == '#') return -1;
    return i*w + j;
}

bool exist[MN], vis[MN];
int nxt[MN];
vi adjList[MN];
vi vals[MN];

int freq[MN];
int cur;
int ans;

int st[MN], si;
void checkLoop(int n1){
    if(vis[n1]) return;

    si = 0;
    while(!vis[n1]){
        st[si++] = n1;
        vis[n1] = true;
        n1 = nxt[n1];
        if(n1 == -1) return;
    }

    int start = -1;
    FR(i, si){
        if(st[i] == n1){
            start = i;
            break;
        }
    }
    if(start == -1) return;

    set<int> loop;
    FOR(i, start, si) loop.insert(st[i]);

    FOR(i, start+1, si){
        int n2 = st[i];
        exist[n2] = false;
        nxt[n2] = -3;
        for(int n3 : adjList[n2]) adjList[n1].pb(n3);
        for(int a : vals[n2]) vals[n1].pb(a);
    }
    nxt[n1] = -1;
    UNIQUE(adjList[n1]);
    UNIQUE(vals[n1]);

    vi newAl;
    for(int n2 : adjList[n1]) if(loop.find(n2) == loop.end()) newAl.pb(n2);
    adjList[n1] = newAl;

    /*cerr << "loop";
    FOR(i, start, si) cerr << ' ' << st[i];
    cerr << endl;*/
}

void dfs(int n1){
    for(int a : vals[n1]) cur += !(freq[a]++);
    ans = max(ans, cur);
    for(int n2 : adjList[n1]) dfs(n2);
    for(int a : vals[n1]) cur -= !(--freq[a]);
}

int main(){
    boost();
    cin >> h >> w;
    n = h*w;
    fill(nxt, nxt + n, -2);

    FR(i, h){
        cin >> grid[i];

        FR(j, w){
            exist[i*w + j] = grid[i][j] != '.' && grid[i][j] != '#';

            if(grid[i][j] == '>') nxt[getCell(i, j)] = getCell(i, j+1);
            if(grid[i][j] == '<') nxt[getCell(i, j)] = getCell(i, j-1);
            if(grid[i][j] == '^') nxt[getCell(i, j)] = getCell(i-1, j);
            if(grid[i][j] == 'v') nxt[getCell(i, j)] = getCell(i+1, j);

            if(grid[i][j] == '#'){
                for(auto [dx, dy] : MOVES){
                    int x = i+dx, y = j+dy;
                    int c = getCell(x, y);
                    if(c == -1) continue;
                    vals[c].pb(i*w + j);
                }
            }
        }
    }

    FR(i, n){
        if(exist[i] && nxt[i] != -1) adjList[nxt[i]].pb(i);
    }

    /*dbgArr(exist, n);
    dbgArr(nxt, n);
    FR(i, n) dbgArr(vals[i].begin(), SZ(vals[i]));*/

    FR(i, n) checkLoop(i);

    //FR(i, n) dbgArr(adjList[i].begin(), SZ(adjList[i]));

    FR(i, n) if(nxt[i] == -1) dfs(i);

    cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

4

result:

ok single line: '4'

Test #2:

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

input:

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

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 2ms
memory: 17932kb

input:

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

output:

5

result:

ok single line: '5'

Test #4:

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

input:

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

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 2ms
memory: 16020kb

input:

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

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 2ms
memory: 18056kb

input:

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

output:

6

result:

ok single line: '6'

Test #7:

score: 0
Accepted
time: 2ms
memory: 17928kb

input:

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

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 2ms
memory: 18012kb

input:

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

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 6ms
memory: 16268kb

input:

2 2
>.
.#

output:

0

result:

ok single line: '0'

Test #10:

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

input:

2 2
..
.v

output:

0

result:

ok single line: '0'

Test #11:

score: -100
Wrong Answer
time: 24ms
memory: 29348kb

input:

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

output:

23336

result:

wrong answer 1st lines differ - expected: '41195', found: '23336'