QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #34175 | #4231. Rafting Trip | Heltion# | RE | 42ms | 32612kb | C++20 | 3.3kb | 2022-06-05 21:30:57 | 2022-06-05 21:31:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> vs(n);
for (auto& s : vs) cin >> s;
vector r(n, vector<int>(m)), mk(n, vector<int>(m));
vector f(n * m, -1), vis(n * m, 0), inc(n * m, 0);
for (int i = 0; i < n; i += 1)
for (int j = 0; j < m; j += 1)
if (vs[i][j] != '#' and vs[i][j] != '.')
r[i][j] = 1;
for (int i = 0; i < n; i += 1)
for (int j = 0; j < m; j += 1)
if (r[i][j]) {
if (vs[i][j] == '<')
if (j and r[i][j - 1])
f[i * m + j] = i * m + j - 1;
if (vs[i][j] == '>')
if (j + 1 < m and r[i][j + 1])
f[i * m + j] = i * m + j + 1;
if (vs[i][j] == '^')
if (i and r[i - 1][j])
f[i * m + j] = (i - 1) * m + j;
if (vs[i][j] == 'v')
if (i + 1 < m and r[i + 1][j])
f[i * m + j] = (i + 1) * m + j;
if (f[i * m + j] == -1)
f[i * m + j] = i * m + j;
}
vector<vector<int>> cs;
for (int i = 0; i < n * m; i += 1)
if (f[i] != -1 and not vis[i]) {
vector<int> w;
int j = i;
for (; not vis[j]; j = f[j]) {
vis[j] = 1;
w.push_back(j);
}
if (ranges::count(w, j)) {
int k = 0;
while (w[k] != j) k += 1;
cs.emplace_back(w.begin() + k, w.end());
for (int ci : cs.back()) inc[ci] = 1;
}
}
vector<vector<int>> G(n * m);
for (int i = 0; i < n * m; i += 1)
if (f[i] != -1 and not inc[i])
G[f[i]].push_back(i);
int ans = 0;
vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
for (auto c : cs) {
int pans = 0;
vector<pair<int, int>> vp;
for (int ci : c) {
int x = ci / m, y = ci % m;
for (int j = 0; j < 4; j += 1) {
int kx = x + dx[j], ky = y + dy[j];
if (kx >= 0 and kx < n and ky >= 0 and ky < m) {
if (vs[kx][ky] == '#' and not mk[kx][ky]) {
pans += mk[kx][ky] = 1;
vp.emplace_back(kx, ky);
}
}
}
}
ans = max(ans, pans);
function<void(int)> DFS = [&](int u) {
vector<pair<int, int>> vp;
int x = u / m, y = u % m;
for (int j = 0; j < 4; j += 1) {
int kx = x + dx[j], ky = y + dy[j];
if (kx >= 0 and kx < n and ky >= 0 and ky < m) {
if (vs[kx][ky] == '#' and not mk[kx][ky]) {
pans += mk[kx][ky] = 1;
vp.emplace_back(kx, ky);
}
}
}
ans = max(ans, pans);
for (int v : G[u]) DFS(v);
pans -= vp.size();
for (auto [x, y] : vp) mk[x][y] = 0;
};
for (int ci : c) DFS(ci);
for (auto [x, y] : vp) mk[x][y] = 0;
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3624kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3512kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3676kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 34ms
memory: 29624kb
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
41195
result:
ok single line: '41195'
Test #12:
score: 0
Accepted
time: 36ms
memory: 32612kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24926
result:
ok single line: '24926'
Test #13:
score: 0
Accepted
time: 34ms
memory: 25324kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24924
result:
ok single line: '24924'
Test #14:
score: 0
Accepted
time: 26ms
memory: 16716kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
2056
result:
ok single line: '2056'
Test #15:
score: 0
Accepted
time: 37ms
memory: 18672kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
970
result:
ok single line: '970'
Test #16:
score: 0
Accepted
time: 42ms
memory: 20196kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
687
result:
ok single line: '687'
Test #17:
score: 0
Accepted
time: 38ms
memory: 20496kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
481
result:
ok single line: '481'
Test #18:
score: 0
Accepted
time: 24ms
memory: 18372kb
input:
500 500 .>^v.^<<^<<<<<<....><v#....^.#.^..#.^<<<<#..#.><v.v..>>^<<..###..^<v..#>>>#.....^>^#.##.#......#.....#v#.>v.v#..##.#.^>>>>>v..#.v<..^...^..^#....#..>v.#^<..^^v..^.....vv..v...#^.v>>v#.#.#..#.v.^v<<......^#<.v...v>>^^<^#..^^v.^..^..^...#.#.^...^^<<<...##...v.........^.^.....>>>>>#.....><<<^.....
output:
13
result:
ok single line: '13'
Test #19:
score: 0
Accepted
time: 33ms
memory: 20100kb
input:
500 499 <<<<<#v.^.^v>v<^^.^<>><>^.^v.><^.v^<.^^#..v#>>><<<v^<>>^>>v<<<<^^^^#<>v>^<>>>^>^<<<#^^#v<<<<<<<<v>#v<<v^v.v^<<^<##><<^^<>^<#^^.^#>v^<<^>>>>v^.^>>^<#^>v^#<<<<^><^#.v^>^.^^v<.#^<<<v.v^^^#^<<.>^^#vvv<<^..>#v<.^<<<>>v>>>^.#v#>>#^<<^v<.>^#^.><^<>#^<<^^^^<<<<.><..><<#^<<>>>>>>>^^<>#>v<><#^^><v<><>...
output:
13
result:
ok single line: '13'
Test #20:
score: -100
Runtime Error
input:
499 500 v^^.#<^^^..>^.v^<^<<v>^<<^>^#^^v^.>vv<v.>v.^<<<<<.v.^>>v<^#v##<^<<<vv^^^^^.>^v...#>v#.#v^^>^<<>v>>v#<><v>#vv<>>v^.>v<^<v>^#>^<<<>^>v^^..vv<<<v#<<.^^<<.v^<>^<<v^<><<vvv#<<v.##^><vv^>^>^v^##>v>>>^^v.#>^.^.^#.v<<<<^#.^^<^^#.>v.#^<^^^..v<>v<.#.^.v#v^..#>v<vv<<<<<>#v^v.#>#..><>>^...^.#><^>>>>>>>>...