QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#64971 | #4231. Rafting Trip | triplem5ds# | TL | 43ms | 32912kb | C++17 | 5.0kb | 2022-11-26 02:31:47 | 2022-11-26 02:31:51 |
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];
bool inStack[555][555];
void dfs(int x, int y) {
inStack[x][y]=true;
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) {
bool canGo=true;
if(grid[x][y] == '>' && !isRiver(x,y+1)) {
canGo=false;
}
if(grid[x][y] == '<' && !isRiver(x,y-1)) {
canGo=false;
}
if(grid[x][y] == '^' && !isRiver(x-1,y)) {
canGo=false;
}
if(grid[x][y] == 'v' && !isRiver(x+1,y)) {
canGo=false;
}
cycles.push_back(vector<ii>());
if(canGo) {
bool canStack;
if(grid[x][y] == '>') {
canStack=inStack[x][y+1];
}
if(grid[x][y] == '<') {
canStack=inStack[x][y-1];
}
if(grid[x][y] == '^') {
canStack=inStack[x-1][y];
}
if(grid[x][y] == 'v') {
canStack=inStack[x+1][y];
}
if(!canStack) {
cycles.pop_back();
} else {
int curX=x,curY=y;
do{
cycles.back().pb({curX,curY});
bool ok = true;
if(grid[curX][curY] == '>' && isRiver(curX,curY+1))
curY += 1, ok = false;
else if(grid[curX][curY] == '<' && isRiver(curX,curY-1))
curY -= 1, ok = false;
else if(grid[curX][curY] == '^' && isRiver(curX-1,curY))
curX -= 1, ok = false;
else if(grid[curX][curY] == 'v' && isRiver(curX+1,curY))
curX += 1, ok = false;
}while(curX!=x||curY!=y);
}
} else {
cycles.back().push_back({x,y});
}
for(auto p : cycles.back())
inCycle[p.F][p.S]=true;
}
inStack[x][y]=false;
}
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) {
if(vis[i][j])return 0;
vis[i][j]=true;
int ans = 0;
for(auto v : adj[i][j]) if(!inCycle[v.F][v.S]){
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;
int cnt = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> grid[i][j];
cnt += 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;
memset(vis,0,sizeof vis);
for(auto c : cycles) {
if(ans==cnt)break;
for(auto p : c) {
inCycle[p.F][p.S]=true;
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: 5ms
memory: 11332kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 2ms
memory: 11844kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 12152kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 6ms
memory: 11480kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 5ms
memory: 11296kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 12000kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 0ms
memory: 12356kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 2ms
memory: 12460kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 2ms
memory: 11036kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 4ms
memory: 12100kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 21ms
memory: 25444kb
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
41195
result:
ok single line: '41195'
Test #12:
score: 0
Accepted
time: 43ms
memory: 32912kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24926
result:
ok single line: '24926'
Test #13:
score: -100
Time Limit Exceeded
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...