QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253808 | #4231. Rafting Trip | chen_zexing | AC ✓ | 41ms | 52808kb | C++17 | 3.9kb | 2023-11-17 16:07:04 | 2023-11-17 16:07:05 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int n,m;
char s[505][505];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int cor[256];
int valid(int x,int y){
if(x==0||y==0||x>n||y>m) return 0;
return cor[s[x][y]]!=-1;
}
vector <pair<int,int>> v[505][505],rv[505][505];
int in[505][505],onc[505][505],f[505][505];
vector <pair<int,int>> bl[505][505];
pair<int,int> fa[505][505];
pair<int,int> find(int x,int y){
return fa[x][y]==make_pair(x,y)?fa[x][y]:fa[x][y]=find(fa[x][y].first,fa[x][y].second);
}
int check(int x,int y){
if(x==0||y==0||x>n||y>m) return 0;
return s[x][y]=='#';
}
int ans;
void dfs(int x,int y,int base){
vector <pair<int,int>> cg;
for(int i=0;i<4;i++)
if(check(x+dx[i],y+dy[i])&&!f[x+dx[i]][y+dy[i]])
f[x+dx[i]][y+dy[i]]++,base++,cg.push_back({x+dx[i],y+dy[i]});
for(auto t:rv[x][y]){
if(onc[t.first][t.second]) continue;
dfs(t.first,t.second,base);
}
ans=max(ans,base);
while(cg.size()) f[cg.back().first][cg.back().second]=0,cg.pop_back();
}
int main() {
int T = 1, kase = 0;
//cin >> T;
while (T--) {
cin>>n>>m;
memset(cor,-1,sizeof(cor));
cor['>']=0,cor['v']=1,cor['<']=2,cor['^']=3;
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(cor[s[i][j]]!=-1&&valid(i+dx[cor[s[i][j]]],j+dy[cor[s[i][j]]]))
v[i][j].push_back({i+dx[cor[s[i][j]]],j+dy[cor[s[i][j]]]}),rv[i+dx[cor[s[i][j]]]][j+dy[cor[s[i][j]]]].push_back({i,j}),in[i+dx[cor[s[i][j]]]][j+dy[cor[s[i][j]]]]++;
else if(cor[s[i][j]]!=-1) v[i][j].push_back({i,j}),rv[i][j].push_back({i,j}),in[i][j]++;
}
queue <pair<int,int>> q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
onc[i][j]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(cor[s[i][j]]!=-1&&in[i][j]==0)
onc[i][j]=0,q.push({i,j});
while(!q.empty()){
auto temp=q.front();
q.pop();
for(auto t:v[temp.first][temp.second]){
in[t.first][t.second]--;
if(!in[t.first][t.second]) q.push({t.first,t.second}),onc[t.first][t.second]=0;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(cor[s[i][j]]!=-1)
fa[i][j]={i,j};
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(onc[i][j]&&cor[s[i][j]]!=-1){
//cout<<i<<" "<<j<<endl;
auto x=find(i,j),y=find(v[i][j][0].first,v[i][j][0].second);
if(x!=y) fa[y.first][y.second]=x;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(onc[i][j]&&cor[s[i][j]]!=-1)
bl[find(i,j).first][find(i,j).second].push_back({i,j});
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(onc[i][j]&&cor[s[i][j]]!=-1&&fa[i][j]==make_pair(i,j)){
int base=0;
for(auto t:bl[i][j]){
for(int k=0;k<4;k++)
if(check(t.first+dx[k],t.second+dy[k])&&!f[t.first+dx[k]][t.second+dy[k]])
f[t.first+dx[k]][t.second+dy[k]]=1,base++;
}
for(auto t:bl[i][j])
dfs(t.first,t.second,base);
for(auto t:bl[i][j]){
for(int k=0;k<4;k++)
if(check(t.first+dx[k],t.second+dy[k]))
f[t.first+dx[k]][t.second+dy[k]]=0;
}
}
printf("%d\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 25720kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 25996kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 25400kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 2ms
memory: 25144kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 25664kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 26644kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 0ms
memory: 25232kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 0ms
memory: 26312kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 2ms
memory: 25024kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 2ms
memory: 26532kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 34ms
memory: 47464kb
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
41195
result:
ok single line: '41195'
Test #12:
score: 0
Accepted
time: 29ms
memory: 52808kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24926
result:
ok single line: '24926'
Test #13:
score: 0
Accepted
time: 27ms
memory: 45728kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24924
result:
ok single line: '24924'
Test #14:
score: 0
Accepted
time: 33ms
memory: 39160kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
2056
result:
ok single line: '2056'
Test #15:
score: 0
Accepted
time: 35ms
memory: 40224kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
970
result:
ok single line: '970'
Test #16:
score: 0
Accepted
time: 41ms
memory: 39556kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
687
result:
ok single line: '687'
Test #17:
score: 0
Accepted
time: 41ms
memory: 39220kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
481
result:
ok single line: '481'
Test #18:
score: 0
Accepted
time: 35ms
memory: 35072kb
input:
500 500 .>^v.^<<^<<<<<<....><v#....^.#.^..#.^<<<<#..#.><v.v..>>^<<..###..^<v..#>>>#.....^>^#.##.#......#.....#v#.>v.v#..##.#.^>>>>>v..#.v<..^...^..^#....#..>v.#^<..^^v..^.....vv..v...#^.v>>v#.#.#..#.v.^v<<......^#<.v...v>>^^<^#..^^v.^..^..^...#.#.^...^^<<<...##...v.........^.^.....>>>>>#.....><<<^.....
output:
13
result:
ok single line: '13'
Test #19:
score: 0
Accepted
time: 39ms
memory: 39084kb
input:
500 499 <<<<<#v.^.^v>v<^^.^<>><>^.^v.><^.v^<.^^#..v#>>><<<v^<>>^>>v<<<<^^^^#<>v>^<>>>^>^<<<#^^#v<<<<<<<<v>#v<<v^v.v^<<^<##><<^^<>^<#^^.^#>v^<<^>>>>v^.^>>^<#^>v^#<<<<^><^#.v^>^.^^v<.#^<<<v.v^^^#^<<.>^^#vvv<<^..>#v<.^<<<>>v>>>^.#v#>>#^<<^v<.>^#^.><^<>#^<<^^^^<<<<.><..><<#^<<>>>>>>>^^<>#>v<><#^^><v<><>...
output:
13
result:
ok single line: '13'
Test #20:
score: 0
Accepted
time: 41ms
memory: 39296kb
input:
499 500 v^^.#<^^^..>^.v^<^<<v>^<<^>^#^^v^.>vv<v.>v.^<<<<<.v.^>>v<^#v##<^<<<vv^^^^^.>^v...#>v#.#v^^>^<<>v>>v#<><v>#vv<>>v^.>v<^<v>^#>^<<<>^>v^^..vv<<<v#<<.^^<<.v^<>^<<v^<><<vvv#<<v.##^><vv^>^>^v^##>v>>>^^v.#>^.^.^#.v<<<<^#.^^<^^#.>v.#^<^^^..v<>v<.#.^.v#v^..#>v<vv<<<<<>#v^v.#>#..><>>^...^.#><^>>>>>>>>...
output:
12
result:
ok single line: '12'
Test #21:
score: 0
Accepted
time: 39ms
memory: 40720kb
input:
500 500 ^v>>v>v<>>>^#>v<^<>>>>v<<<^v.>^><.v>v<>^>vv^v>>><.>^v>>#^<<<>^<vv^^>>>v<v.^^v>v<vv<^>vv^<<vv<^^^^>>^^<^>>^^>>#<v^>v>>^<v<#<<vv<<<<<<<<<<<<<<<<<<^^v>^^<^^^v^<<#><<><>^>^>>>v<>>v><<^^<v^v<>>>^<v>>^vv>>v>>>v>v.v.v<v>#^<<<<<<<<<<.>v>^<<<<><^v<>v#<.^>^>^vv.v<>^v#<##^v^>^#v<v<<<<>>>#^>v>>>>>v^^>>^...
output:
11
result:
ok single line: '11'
Test #22:
score: 0
Accepted
time: 3ms
memory: 29320kb
input:
500 500 ######<##############^#####>########v##########v###############################<######<#####>######v########################v####v##########>######v####<##########^#<##################<#####<########v#######<^####^v#####################^v####>#########^###########.v####<##########v##########...
output:
10
result:
ok single line: '10'
Test #23:
score: 0
Accepted
time: 41ms
memory: 40904kb
input:
500 500 <^^<^>><##<v>^>>#<^>v<^v<^^^<<><^^^<^v<^<^^^v#v<<<vv<vv^>>>>>>><vv<<<<>vv^^<^^>><<^<^>^<>^><v>^>^vv>^>^><<^v>^<<>vvv><>>>>>^vv>>#<>>>^^<v<<<^>v^^^<#<<^v^<<>>>>><##^>>#<<<<<<<<^><<<<<<^v^vv.^><>v^^v<v^>vv#^<<<^<<>#>^>>v>^>^^<^>>>^<v<<<v#v^>^^^<^<>^^<vv<<<#>v<v<^v^#^^>>>>^v^^<<>>#>>v<<<<v^<vv>...
output:
14
result:
ok single line: '14'
Test #24:
score: 0
Accepted
time: 3ms
memory: 26728kb
input:
500 2 <v .# .# vv #< v^ <> <^ v. #> ># v^ #< ^# #< >v <> ^. #. << #< >> ># >> #< #v ^# << #^ #v #^ ^. ^# v# ## #> << #^ v^ <v ^# ^> ># .v #^ <# ## .v ># ## ^# ^< ^^ <# .> <^ v< >< <v #v ## #> #> ## ## ^# v> >< .^ v# #^ v> <v ## ## #> >v #v >< .# #. ^# #. ># v< ># #< <^ ^# #. <> #^ .v ## .v .v .# >> ...
output:
6
result:
ok single line: '6'
Test #25:
score: 0
Accepted
time: 0ms
memory: 25928kb
input:
2 500 v##v#>>>>^>>#.##<<.>>^#.v^>^^>##^>^^##v^^#.^<#<###<##v#^>^^.v>v#<^<<##^#^.#<##>#>>#v#>^#vv.^v#>v.####.>#.>>v#<.>#^..#<v##>>>^#v###^<#^#<#^^#>v^>###>>>><#^#v>v.v<^.#v.v##<.####<<<^#>^#^#<#>v#>#>^#>##.>>>^^<##<^^<v<...#v#.#<>>>>#.##.v#<.##.^#<^>#<<vv^>^#^..#<^##^^#<<##.vv<v^#<><.#<<.^^##^.#<v.##...
output:
5
result:
ok single line: '5'
Test #26:
score: 0
Accepted
time: 15ms
memory: 49712kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
31270
result:
ok single line: '31270'
Test #27:
score: 0
Accepted
time: 12ms
memory: 52324kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
123584
result:
ok single line: '123584'
Test #28:
score: 0
Accepted
time: 20ms
memory: 35072kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
331
result:
ok single line: '331'
Test #29:
score: 0
Accepted
time: 16ms
memory: 34908kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
1234
result:
ok single line: '1234'
Test #30:
score: 0
Accepted
time: 20ms
memory: 34820kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
281
result:
ok single line: '281'
Test #31:
score: 0
Accepted
time: 20ms
memory: 34920kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
996
result:
ok single line: '996'