QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#77777#4231. Rafting TripidontreallyknowWA 2ms10520kbC++174.1kb2023-02-15 16:28:372023-02-15 16:28:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-15 16:28:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10520kb
  • [2023-02-15 16:28:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fi first
#define se second
template<typename... T>
void dbg(T... t) {initializer_list<int>{(cerr << t << ' ', 0)...}; cerr << '\n';}
const int mx = 505;
int r,c,vis[mx][mx], col[mx][mx], cyc[mx][mx];
string g[mx];
pii nxt(pii x, char c) {
    if (c == '<') x.se--;
    else if (c == '>') x.se++;
    else if (c == '^') x.fi--;
    else if (c == 'v') x.fi++;
    else {
        assert(false);
    }
    return x;
}
bool ok(int x, int y) {
    return x >= 0 && x < r && y >= 0 && y < c;
}
bool ok(pii x) {
    return x.fi >= 0 && x.fi < r && x.se >= 0 && x.se < c;
}
int conv(pii p) {
    return c*p.fi+p.se;
}
pii conv(int x) {
    return {x/c, x%c};
}
vector<int> radj[mx*mx];
int ans = 0;
set<pii> spots;
vector<int> dx = {1,0,-1,0};
vector<int> dy = {0,1,0,-1};
void dfs(int sq) { // assert invariants?
    pii pos = conv(sq);
    set<pii> ins;
    for (int q = 0; q < 4; q++) {
        int nx = pos.fi+dx[q], ny = pos.se+dy[q];
        if (ok(nx,ny) && g[nx][ny] == '#') {
            if (spots.find({nx,ny}) == spots.end()) {
                ins.insert({nx,ny});
                spots.insert({nx,ny});
            }
        }
    }
    ans = max<int>(ans, spots.size());
    for (auto rpos : radj[sq]) {
        dfs(rpos);
    }
    for (auto p : ins) {
        spots.erase(p);
    }
}
int main() {
    cin >> r >> c;
    for (int q = 0; q < r; q++) cin >> g[q];
    vector<pii> term;
    vector<vector<pii>> cycles;
    for (int q = 0; q < r; q++) {
        for (int w = 0; w < c; w++) {
            if (g[q][w] == '#' || g[q][w] == '.' || col[q][w]) continue;
            pii cur{q,w};
            while (col[cur.fi][cur.se] != 1) {
                col[cur.fi][cur.se] = 1;
                pii nc = nxt(cur, g[cur.fi][cur.se]);
                if (!ok(nc) || g[nc.fi][nc.se] == '#' || g[nc.fi][nc.se] == '.') {
                    term.push_back(cur);
                    break;
                } else if (col[nc.fi][nc.se] == 2) {
                    break;
                } else if (col[nc.fi][nc.se] == 1) {
                    pii tmp = cur;
                    cycles.emplace_back();
                    while (col[tmp.fi][tmp.se] != 2) {
                        cycles.back().push_back(tmp);
                        col[tmp.fi][tmp.se] = 2;
                        cyc[tmp.fi][tmp.se] = 1;
                        tmp = nxt(tmp,g[tmp.fi][tmp.se]);
                    }
                    break;
                } else {
                    cur = nc;
                }
            }
            cur = pii{q,w};
            while (col[cur.fi][cur.se] != 2) {
                col[cur.fi][cur.se] = 2;
                pii nc = nxt(cur, g[cur.fi][cur.se]);
                if (!ok(nc) || g[nc.fi][nc.se] == '#' || g[nc.fi][nc.se] == '.') {
                    break;
                } else if (col[nc.fi][nc.se] == 2) {
                    break;
                } else {
                    assert(col[nc.fi][nc.se] == 1);
                    cur = nc;
                }
            }
        }
    }
    for (int q = 0; q < r; q++) {
        for (int w = 0; w < c; w++) {
            if (g[q][w] != '#' && g[q][w] != '.') {
                pii nc = nxt({q,w},g[q][w]);
                if (ok(nc) && g[nc.fi][nc.se] != '#' && g[nc.fi][nc.se] != '.') {
                    radj[conv(nc)].push_back(conv({q,w}));
                }
            }
        }
    }
    for (auto p : term) {
        dfs(conv(p));
    }
    for (const auto& cycle : cycles) {
        spots.clear();
        vector<int> roots;
        for (auto pos : cycle) {
            for (int e = 0; e < 4; e++) {
                int nx = pos.fi+dx[e], ny = pos.se+dy[e];
                if (ok(nx,ny) && g[nx][ny] == '#') spots.insert({nx,ny});
            }
            for (auto rpos : radj[conv(pos)]) {
                pii place = conv(rpos);
                if (!cyc[place.fi][place.se]) roots.push_back(rpos);
            }
        }
        for (auto r : roots) {
            dfs(r);
        }
    }
    cout << ans << '\n';
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9656kb

input:

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

output:

4

result:

ok single line: '4'

Test #2:

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

input:

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

output:

2

result:

ok single line: '2'

Test #3:

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

input:

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

output:

0

result:

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