QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#375825 | #4231. Rafting Trip | 8BQube# | WA | 2ms | 9872kb | C++20 | 5.2kb | 2024-04-03 16:16:33 | 2024-04-03 16:16:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
string mp[505];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};
int mapping[100000], vis[505][505], tag[505][505], indeg[505][505], wei[505][505], dp[505][505];
pii bln[505][505];
int in[505][505], out[505][505], dft;
vector<pii> G[505][505];
void dfs(int x, int y, int p, int q) {
in[x][y] = ++dft, bln[x][y] = pii(p, q);
for (auto [a, b] : G[x][y])
if (!in[a][b])
dfs(a, b, p, q);
out[x][y] = dft;
}
bool strict_ancestor(int x, int y, int a, int b) {
return in[x][y] < in[a][b] && out[x][y] >= out[a][b];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
mapping['^'] = 0;
mapping['v'] = 1;
mapping['>'] = 2;
mapping['<'] = 3;
int r, c;
cin >> r >> c;
for (int i = 0; i < r; ++i)
cin >> mp[i];
auto river = [&](int a, int b) {
if (a < 0 || a >= r || b < 0 || b >= c || mp[a][b] == '#' || mp[a][b] == '.') return false;
return true;
};
auto sight = [&](int a, int b) {
if (a < 0 || a >= r || b < 0 || b >= c) return false;
return mp[a][b] == '#';
};
auto add = [&](int a, int b, int v) {
if (!river(a, b)) return;
indeg[a][b] += v;
};
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
if (river(i, j)) {
int d = mapping[int(mp[i][j])];
add(i + dx[d], j + dy[d], 1);
}
queue<pii> q;
auto check = [&](int a, int b) {
if (river(a, b) && !indeg[a][b])
q.emplace(a, b);
};
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
check(i, j);
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
int d = mapping[int(mp[i][j])];
add(i + dx[d], j + dy[d], -1);
check(i + dx[d], j + dy[d]);
}
vector<pii> root;
auto add_edge = [&](int a, int b, int x, int y) {
G[a][b].pb(pii(x, y));
};
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
if (river(i, j) && !indeg[i][j]) {
bln[i][j] = pii(i, j);
int d = mapping[int(mp[i][j])];
if (river(i + dx[d], j + dy[d]) && !indeg[i + dx[d]][j + dy[d]])
add_edge(i + dx[d], j + dy[d], i, j);
else
root.pb(pii(i, j));
}
else if (river(i, j) && indeg[i][j] && !vis[i][j]) {
for (int x = i, y = j; !vis[x][y];) {
vis[x][y] = 1, bln[x][y] = pii(i, j);
int d = mapping[int(mp[x][y])];
x += dx[d], y += dy[d];
}
}
for (auto [x, y] : root) {
int d = mapping[int(mp[x][y])];
int a = x, b = y;
if (river(x + dx[d], y + dy[d]))
tie(a, b) = bln[x + dx[d]][y + dy[d]];
dfs(x, y, a, b);
}
int tp = 0;
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
if (sight(i, j)) {
vector<pii> riv;
for (int d = 0; d < 4; ++d)
if (river(i + dx[d], j + dy[d]))
riv.pb(pii(i + dx[d], j + dy[d]));
++tp;
for (auto [x, y] : riv)
if (indeg[x][y] && tag[bln[x][y].X][bln[x][y].Y] != tp) {
wei[bln[x][y].X][bln[x][y].Y] += 1;
tag[bln[x][y].X][bln[x][y].Y] = tp;
}
for (auto [x, y] : riv) {
if (indeg[x][y]) continue;
int flag = (tag[bln[x][y].X][bln[x][y].Y] == tp);
for (auto [a, b] : riv) {
if (indeg[a][b]) continue;
if (strict_ancestor(a, b, x, y))
flag = 1;
}
if (!flag)
wei[x][y] += 1;
}
}
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
indeg[i][j] = 0;
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
if (river(i, j)) {
int d = mapping[int(mp[i][j])];
add(i + dx[d], j + dy[d], 1);
}
int ans = 0;
auto add2 = [&](int a, int b, int v, int dpv) {
if (!river(a, b)) return;
dp[a][b] = max(dp[a][b], dpv);
ans = max(ans, dp[a][b] + wei[bln[a][b].X][bln[a][b].Y]);
indeg[a][b] += v;
};
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
check(i, j);
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
dp[i][j] += wei[i][j];
ans = max(ans, dp[i][j]);
int d = mapping[int(mp[i][j])];
add2(i + dx[d], j + dy[d], -1, dp[i][j]);
check(i + dx[d], j + dy[d]);
}
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9872kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9792kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 7788kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
0
result:
wrong answer 1st lines differ - expected: '5', found: '0'