QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353039 | #4231. Rafting Trip | PetroTarnavskyi# | WA | 1ms | 7672kb | C++20 | 2.8kb | 2024-03-13 20:00:37 | 2024-03-13 20:00:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 507;
string grid[N];
int n, m;
bool ok(int i, int j)
{
return 0 <= i && i < n && 0 <= j && j < m;
}
string moves = "<v>^";
PII d[4] = {MP(0, -1), MP(1, 0), MP(0, 1), MP(-1, 0)};
PII to[N][N];
vector<PII> from[N][N];
bool used[N][N];
int was[N][N];
int cnt = 0;
int ans = 0;
void add(int i, int j)
{
FOR(k, 0, 4)
{
int ni = i + d[k].F;
int nj = j + d[k].S;
if(ok(ni, nj) && grid[ni][nj] == '#')
{
if(was[ni][nj] == 0)
cnt++;
was[ni][nj]++;
}
}
ans = max(ans, cnt);
}
void remove(int i, int j)
{
FOR(k, 0, 4)
{
int ni = i + d[k].F;
int nj = j + d[k].S;
if(ok(ni, nj) && grid[ni][nj] == '#')
{
was[ni][nj]--;
if(was[ni][nj] == 0)
cnt--;
}
}
}
void dfs(PII v)
{
add(v.F, v.S);
used[v.F][v.S] = 1;
for(auto u : from[v.F][v.S])
{
if(!used[u.F][u.S])
dfs(u);
}
remove(v.F, v.S);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
FOR(i, 0, n)
{
cin >> grid[i];
FOR(j, 0, m)
{
to[i][j] = {-1, -1};
if(grid[i][j] == '.' || grid[i][j] == '#')
{
used[i][j] = 1;
}
else
used[i][j] = 0;
}
}
FOR(i, 0, n)
{
FOR(j, 0, m)
{
if(used[i][j])
continue;
FOR(k, 0, 4)
{
//cerr << grid[i][j] << " " << moves[k] << "\n";
if(grid[i][j] != moves[k])
continue;
int ni = i + d[k].F;
int nj = j + d[k].S;
//cerr << i << " " << j << " " << ni << " " << nj << "\n";
if(ok(ni, nj) && !used[ni][nj])
{
to[i][j] = {ni, nj};
// cerr << i << " " << j << " " << ni << " " << nj << "\n";
from[ni][nj].PB({i, j});
}
}
}
}
FOR(i, 0, n)
{
FOR(j, 0, m)
{
if(used[i][j])
continue;
PII v = {i, j};
vector<PII> st;
while(v.F != -1 && !used[v.F][v.S])
{
st.PB(v);
used[v.F][v.S] = 1;
v = to[v.F][v.S];
}
for(auto u : st)
used[u.F][u.S] = 0;
vector<PII> cyc;
if(v.F == -1)
{
cyc.PB(st.back());
}
else
{
//find cyc
while(st.back() != v)
{
cyc.PB(st.back());
st.pop_back();
}
cyc.PB(v);
}
for(auto u : cyc)
{
// cout << u.F << " " << u.S << "\n";
used[u.F][u.S] = 1;
}
//cout << "-----\n";
for(auto w : cyc)
{
dfs(w);
}
}
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7672kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 5940kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
2
result:
wrong answer 1st lines differ - expected: '5', found: '2'