QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#64961 | #4231. Rafting Trip | triplem5ds# | WA | 6ms | 13524kb | C++23 | 3.8kb | 2022-11-26 01:58:59 | 2022-11-26 01:59:02 |
Judging History
answer
/// Brrrr Brrrr
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define F first
#define S second
#define f(i, a, b) for(int i = a; i < b; i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define mp(x,y) make_pair(x,y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll
using ll = long long;
using ii = pair<int, int>;
using ull = unsigned long long;
const int N = 1e5+5, LG = 18, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-7;
const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
int n, m;
char grid[555][555];
bool inCycle[555][555];
bool vis[555][555];
bool isRiver(int i, int j) {
return grid[i][j] == '>' || grid[i][j] == '<' || grid[i][j] == 'v' || grid[i][j] == '^';
}
vector<vector<ii>> cycles;
int cnt[555][555], cur;
vector<ii> adj[555][555];
void dfs(int x, int y) {
vis[x][y] = true;
bool can=true;
if(grid[x][y] == '>' && isRiver(x,y+1)) {
if(!vis[x][y+1])
dfs(x,y+1);
can = false;
adj[x][y+1].pb({x,y});
}
if(grid[x][y] == '<' && isRiver(x,y-1)) {
if(!vis[x][y-1])
dfs(x,y-1);
can = false;
adj[x][y-1].pb({x,y});
}
if(grid[x][y] == '^' && isRiver(x-1,y)) {
if(!vis[x-1][y])
dfs(x-1,y);
can = false;
adj[x-1][y].pb({x,y});
}
if(grid[x][y] == 'v' && isRiver(x+1,y)) {
if(!vis[x+1][y])
dfs(x+1,y);
can = false;
adj[x+1][y].pb({x,y});
}
if(can) {
cycles.push_back(vector<ii>());
int curX=x,curY=y;
do{
inCycle[curX][curY]=true;
cycles.back().pb({curX,curY});
bool ok = true;
if(grid[curX][curY] == '>' && isRiver(curX,curY+1))
curY += 1, ok = false;
if(grid[curX][curY] == '<' && isRiver(curX,curY-1))
curY -= 1, ok = false;
if(grid[curX][curY] == '^' && isRiver(curX-1,curY))
curX -= 1, ok = false;
if(grid[curX][curY] == 'v' && isRiver(curX+1,curY))
curX += 1, ok = false;
if(ok && make_pair(curX,curY) != make_pair(x,y)) {
cycles.pop_back();
break;
}
}while(curX!=x||curY!=y);
}
}
void addC(int i, int j, int v) {
if(grid[i][j] != '#') return;
cur -= cnt[i][j] > 0;
cnt[i][j] += v;
cur += cnt[i][j] > 0;
}
void add(int i, int j, int v) {
f(k,0,4) {
int nx = i + dx[k];
int ny = j + dy[k];
addC(nx,ny,v);
}
}
int dfsTree(int i, int j) {
int ans = 0;
for(auto v : adj[i][j]) {
add(v.F, v.S, +1);
ans = max(ans, dfsTree(v.F, v.S));
add(v.F, v.S, -1);
}
return max(ans, cur);
}
void doWork() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> grid[i][j];
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(isRiver(i,j) && !vis[i][j]) {
dfs(i,j);
}
int ans = 0;
for(auto c : cycles) {
for(auto p : c) {
add(p.F,p.S,+1);
}
for(auto p : c)ans = max(ans, dfsTree(p.F,p.S));
for(auto p : c)
add(p.F,p.S,-1);
}
cout << ans << '\n';
}
int32_t main() {
#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif // ONLINE_JUDGE
int t = 1;
// cin >> t;
while (t--) {
doWork();
}
return 0;
}
///Look at my code ya codeomk
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 13344kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 2ms
memory: 13524kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 12412kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
0
result:
wrong answer 1st lines differ - expected: '5', found: '0'