QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91530 | #4231. Rafting Trip | FHQY | TL | 13ms | 14296kb | C++17 | 2.7kb | 2023-03-29 02:15:07 | 2023-03-29 02:15:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=509;
int ans,res,f1,f2,p1,p2,p3,p4,xx,yy,pre,px,py,f;
int sign[maxn][maxn];
int mp[maxn][maxn];
int d[maxn][maxn];
//int pd[maxn][maxn];
int sx[4]={-1,0,1,0};
int sy[4]={0,1,0,-1};
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
bool check(int x,int y)
{
if(mp[x][y]!=-1)
{
p1=mp[x][y];
p2=(p1+2)%4;
if(mp[x+sx[p1]][y+sy[p1]]==-1)
return true;
}
return false;
}
void dfs1(int x,int y)
{
// if(sign[x][y])
// return;
sign[x][y]=1;
int bid[4];
for(int t=0;t<4;t++)
{
bid[t]=d[x+sx[t]][y+sy[t]];
d[x+sx[t]][y+sy[t]]=0;
ans+=bid[t];
}
for(int t=0;t<4;t++)
{
p1=(t+2)%4;
if(mp[x+sx[t]][y+sy[t]]==p1)
dfs1(x+sx[t],y+sy[t]);
}
res=max(res,ans);
for(int t=0;t<4;t++)
{
d[x+sx[t]][y+sy[t]]=bid[t];
ans-=bid[t];
}
return;
}
void dfs2(int x,int y)
{
// if(d[x][y]==-1)
// return;
if(sign[x][y])
{
f1=x;
f2=y;
return;
}
sign[x][y]=1;
p1=mp[x][y];
dfs2(x+sx[p1],y+sy[p1]);
sign[x][y]=0;
return;
}
void dfs3(int x,int y)
{
sign[x][y]=1;
if(x==f1&&y==f2&&f)
{
px=x;
py=y;
int st=0;
while(st==0||(!(px==f1&&py==f2)))
{
st++;
for(int t=0;t<4;t++)
{
if(!sign[x+sx[t]][y+sy[t]]&&mp[x+sx[t]][y+sy[t]]!=-1&&mp[x+sx[t]][y+sy[t]]==(t+2)%4)
{
dfs1(x+sx[t],y+sy[t]);
}
}
}
return;
}
f=1;
p1=mp[x][y];
int bid[4];
for(int t=0;t<4;t++)
{
bid[t]=d[x+sx[t]][y+sy[t]];
d[x+sx[t]][y+sy[t]]=0;
ans+=bid[t];
}
dfs3(x+sx[p1],y+sy[p1]);
res=max(res,ans);
for(int t=0;t<4;t++)
{
d[x+sx[t]][y+sy[t]]=bid[t];
ans-=bid[t];
}
return;
}
int main()
{
// freopen("rand.out","r",stdin);
// freopen("my.out","w",stdout);
int a,b;
res=0;
cin>>a>>b;
memset(mp,-1,sizeof(mp));
for(int x=1;x<=a;x++)
{
string str;
cin>>str;
for(int t=1;t<=b;t++)
{
if(str[t-1]=='>')
mp[x][t]=1;
else if(str[t-1]=='^')
mp[x][t]=0;
else if(str[t-1]=='<')
mp[x][t]=3;
else if(str[t-1]=='v')
mp[x][t]=2;
else if(str[t-1]=='#')
d[x][t]=1;
}
}
for(int x=1;x<=a;x++)
{
for(int y=1;y<=b;y++)
{
if(check(x,y))
{
int bid[4];
ans=0;
dfs1(x,y);
res=max(res,ans);
}
}
}
for(int x=1;x<=a;x++)
{
for(int y=1;y<=b;y++)
{
if(!sign[x][y]&&mp[x][y]!=-1)
{
dfs2(x,y);
ans=0;
f=0;
dfs3(f1,f2);
}
}
}
cout<<res<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5476kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 3ms
memory: 4516kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5472kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 3ms
memory: 5528kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 4484kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 5540kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4540kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4456kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 3ms
memory: 4492kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 3ms
memory: 4440kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 13ms
memory: 11588kb
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
41195
result:
ok single line: '41195'
Test #12:
score: 0
Accepted
time: 13ms
memory: 14296kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24926
result:
ok single line: '24926'
Test #13:
score: -100
Time Limit Exceeded
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...