QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#349780 | #4231. Rafting Trip | LaStataleBlue | TL | 1ms | 4344kb | C++23 | 2.5kb | 2024-03-10 05:24:37 | 2024-03-10 05:24:38 |
Judging History
answer
#include <string>
#include <bits/functexcept.h>
#include <iosfwd>
#include <bits/cxxabi_forced.h>
#include <bits/functional_hash.h>
#pragma push_macro("__SIZEOF_LONG__")
#pragma push_macro("__cplusplus")
#define __SIZEOF_LONG__ __SIZEOF_LONG_LONG__
#define unsigned unsigned long
#define __cplusplus 201102L
#define __builtin_popcountl __builtin_popcountll
#define __builtin_ctzl __builtin_ctzll
#include <bitset>
#pragma pop_macro("__cplusplus")
#pragma pop_macro("__SIZEOF_LONG__")
#undef unsigned
#undef __builtin_popcountl
#undef __builtin_ctzl
#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]];
}
vis[nodo]=3;
};
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: 4144kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4104kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4344kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: -100
Time Limit Exceeded
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...