QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#77777 | #4231. Rafting Trip | idontreallyknow | WA | 2ms | 10520kb | C++17 | 4.1kb | 2023-02-15 16:28:37 | 2023-02-15 16:28:40 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'