QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#349757 | #4231. Rafting Trip | LaStataleBlue | TL | 1ms | 4548kb | C++23 | 2.0kb | 2024-03-10 05:08:30 | 2024-03-10 05:08:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
void solve([[maybe_unused]] int t){
const int N = 500;
int r,c;
cin>>r>>c;
auto id = [&](int x,int y)->int{
if(x<0 || x>=r || y<0 || y>=c)return -1;
return x*c+y;
};
vector opz(r*c,bitset<N*N>());
vector mat(r,vector(c,'.'));
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cin>>mat[i][j];
}
}
const vector<array<int,2>> dir = {{-1,0},{1,0},{0,-1},{0,1}};
vector succ(r*c,-1);
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(mat[i][j]=='>' && id(i,j+1)!=-1 && mat[i][j+1]!='#' && mat[i][j+1]!='.')succ[id(i,j)]=id(i,j+1);
if(mat[i][j]=='<' && id(i,j-1)!=-1 && mat[i][j-1]!='#' && mat[i][j-1]!='.')succ[id(i,j)]=id(i,j-1);
if(mat[i][j]=='^' && id(i-1,j)!=-1 && mat[i-1][j]!='#' && mat[i-1][j]!='.')succ[id(i,j)]=id(i-1,j);
if(mat[i][j]=='v' && id(i+1,j)!=-1 && mat[i+1][j]!='#' && mat[i+1][j]!='.')succ[id(i,j)]=id(i+1,j);
for(auto [dx,dy] : dir){
if(id(i+dx,j+dy)!=-1 && mat[i+dx][j+dy]=='#'){
opz[id(i,j)][id(i+dx,j+dy)]=1;
}
}
}
}
vector vis(r*c,0);
auto dfs = [&](auto &dfs,int nodo)->void{
if(vis[nodo]==3)return;
vis[nodo]++;
if(succ[nodo]!=-1){
dfs(dfs,succ[nodo]);
opz[nodo]|=opz[succ[nodo]];
}
};
int ans=0;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(mat[i][j]!='#'&& mat[i][j]!='.'){
dfs(dfs,id(i,j));
ans=max(ans,(int)opz[id(i,j)].count());
}
}
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve(i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4184kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3956kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4124kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4548kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3888kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4036kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: -100
Time Limit Exceeded
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...