QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#415630#4231. Rafting Triplittlecat#WA 1ms3760kbC++143.0kb2024-05-21 07:11:232024-05-21 07:11:23

Judging History

你现在查看的是最新测评结果

  • [2024-05-21 07:11:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3760kb
  • [2024-05-21 07:11:23]
  • 提交

answer

#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
#include <vector>
#define pb push_back
template<class C> using vc=vector<C>;
#define For(i,a,b) for(int i=(a);i<(b);i++)
#define smax(a,b) a=max(a,b)
#define f first
#define s second
typedef double d;
typedef pair<int,int> pi;

const int mx=502;
int n,m; char g[mx][mx];
bool x[mx][mx], y[mx][mx];
bool v[mx][mx], V[mx][mx], tmp[mx][mx];
int ans, curans;
pi nxt(int i, int j)
{
    if(g[i][j]=='v') return {i+1,j};
    if(g[i][j]=='^') return {i-1,j};
    if(g[i][j]=='<') return {i,j-1};
    if(g[i][j]=='>') return {i,j+1};
    return {i,j};
}
int vis(int i, int j)
{
    int ans=0;
    if(y[i-1][j]&&!v[i-1][j]) ans+=1, v[i-1][j]=1, curans++;
    if(y[i+1][j]&&!v[i+1][j]) ans+=2, v[i+1][j]=1, curans++;
    if(y[i][j-1]&&!v[i][j-1]) ans+=4, v[i][j-1]=1, curans++;
    if(y[i][j+1]&&!v[i][j+1]) ans+=8, v[i][j+1]=1, curans++;
    return ans;
}
void unvis(int i, int j, int k)
{
    if(k&1) v[i-1][j]=0, curans--;
    if(k&2) v[i+1][j]=0, curans--;
    if(k&4) v[i][j-1]=0, curans--;
    if(k&8) v[i][j+1]=0, curans--;
}
void solve(int i, int j)
{
    int k=vis(i,j); ans=max(ans,curans); V[i][j]=1;
    if(g[i-1][j]=='v') solve(i-1,j);
    if(g[i+1][j]=='^') solve(i+1,j);
    if(g[i][j-1]=='>') solve(i,j-1);
    if(g[i][j+1]=='<') solve(i,j+1);
    unvis(i,j,k);
}
void solve1(int i, int j)
{
    if(g[i-1][j]=='v'&&!V[i-1][j]) solve(i-1,j);
    if(g[i+1][j]=='^'&&!V[i+1][j]) solve(i+1,j);
    if(g[i][j-1]=='>'&&!V[i][j-1]) solve(i,j-1);
    if(g[i][j+1]=='<'&&!V[i][j+1]) solve(i,j+1);
}
int main()
{
    cin.sync_with_stdio(0), cin.tie(0), cout.sync_with_stdio(0), cout.tie(0);
    cin>>n>>m, n+=2, m+=2;
    For(i,0,n) For(j,0,m) g[i][j]='.', x[i][j]=1;
    For(i,1,n-1) For(j,1,m-1) cin>>g[i][j],
        y[i][j]=g[i][j]=='#', x[i][j]=g[i][j]=='.'||y[i][j];
    For(i,0,n) For(j,0,m)
    {
        if(x[i][j]||V[i][j]) continue;
        //follow chain
        pi cur(i,j);
        while(1)
        {
            tmp[cur.f][cur.s]=1;
            pi ncur=nxt(cur.f,cur.s);
            if(x[ncur.f][ncur.s])
            {
// cerr<<"Tree "<<cur.f<<' '<<cur.s<<' '<<curans<<' '<<ans<<'\n'<<flush;
                solve(cur.f,cur.s);
                break;
            }
            cur=ncur;
            if(tmp[cur.f][cur.s])
            {
// cerr<<"Loop "<<cur.f<<' '<<cur.s<<' '<<curans<<' '<<ans<<'\n'<<flush;
                //cycle
                vc<pi> v1;
                pi stop=cur;
                while(1)
                {
                    v1.pb(cur), V[cur.f][cur.s]=1;
                    cur=nxt(cur.f,cur.s);
                    if(cur==stop) break;
                }
                vc<int> v2;
                for(pi p:v1) v2.pb(vis(p.f,p.s));
                for(pi p:v1) solve1(p.f,p.s);
                for(int t=0; t<v1.size(); t++) unvis(v1[t].f,v1[t].s,v2[t]);
                break;
            }
        }
    }
    cout<<ans<<'\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3760kb

input:

5 6
v<<<#v
v#v<.>
>>v<<<
..v##^
#<<<.^

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

4 5
>v<<.
^<..#
#...#
.#>^#

output:

2

result:

ok single line: '2'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3688kb

input:

4 6
>>v#>v
^#>>^v
^<<#v<
.#^<<#

output:

0

result:

wrong answer 1st lines differ - expected: '5', found: '0'