oj.uz

Submission #257966

# Submission time Handle Problem Language Result Execution time Memory
257966 2020-08-05T06:35:54 Z 최은수(#5047) Sandwich (JOI16_sandwich) C++17
35 / 100
 8000 ms 1912 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
int n,m;
char map[420][420];
int par;
int chk[420][420];
int dfs(int x,int y)
{
    if(x<=0||x>n||y<=0||y>m||chk[x][y]==par+2)
        return 0;
    chk[x][y]=par+1;
    bool ch[4];
    for(int i=0;i<4;i++)
        ch[i]=0;
    int ans=2;
    for(int i=-2;i<2;i++)
    {
        int nx=x+i%2;
        int ny=y+(i+1)%2;
        if(chk[nx][ny]!=par+1)
            ch[i+2]=1;
    }
    if(map[x][y]=='N')
    {
        if(ch[1]&&ch[2])
        {
            int r=dfs(x-1,y);
            ans+=r;
            if(r==-1)
                return -1;
            r=dfs(x,y+1);
            ans+=r;
            if(r==-1)
                return -1;
        }
        else if(ch[0]&&ch[3])
        {
            int r=dfs(x,y-1);
            ans+=r;
            if(r==-1)
                return -1;
            r=dfs(x+1,y);
            ans+=r;
            if(r==-1)
                return -1;
        }
        else
            return -1;
    }
    else
    {
        if(ch[0]&&ch[1])
        {
            int r=dfs(x,y-1);
            ans+=r;
            if(r==-1)
                return -1;
            r=dfs(x-1,y);
            ans+=r;
            if(r==-1)
                return -1;
        }
        else if(ch[2]&&ch[3])
        {
            int r=dfs(x,y+1);
            ans+=r;
            if(r==-1)
                return -1;
            r=dfs(x+1,y);
            ans+=r;
            if(r==-1)
                return -1;
        }
        else
            return -1;
    }
    chk[x][y]=par+2;
    return ans;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=0;i++<n;)
        for(int j=0;j++<m;)
            cin>>map[i][j];
    for(int i=0;i++<n;cout<<endl)
    {
        for(int j=0;j++<m;)
        {
            int ans=inf;
            chk[i][j]=par+1;
            int r=dfs(i,j-1);
            if(r!=-1)
            {
                int r2=dfs(i+(map[i][j]=='Z'?-1:1),j);
                if(r2!=-1)
                    ans=min(ans,r2+r);
            }
            par+=2;
            chk[i][j]=par+1;
            r=dfs(i,j+1);
            if(r!=-1)
            {
                int r2=dfs(i+(map[i][j]=='Z'?1:-1),j);
                if(r2!=-1)
                    ans=min(ans,r2+r);
            }
            par+=2;
            cout<<(ans==inf?-1:ans+2)<<' ';
        }
    }
    return 0;
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 9 ms 512 KB Output is correct
7 Correct 71 ms 512 KB Output is correct
8 Correct 89 ms 504 KB Output is correct
9 Correct 43 ms 384 KB Output is correct
10 Correct 92 ms 460 KB Output is correct
11 Correct 171 ms 516 KB Output is correct
12 Correct 57 ms 384 KB Output is correct
13 Correct 156 ms 512 KB Output is correct
14 Correct 152 ms 512 KB Output is correct
15 Correct 76 ms 504 KB Output is correct
16 Correct 50 ms 512 KB Output is correct
17 Correct 67 ms 512 KB Output is correct
18 Correct 62 ms 504 KB Output is correct
19 Correct 66 ms 508 KB Output is correct
20 Correct 56 ms 508 KB Output is correct
21 Correct 59 ms 504 KB Output is correct
22 Correct 52 ms 512 KB Output is correct
23 Correct 50 ms 504 KB Output is correct
24 Correct 145 ms 512 KB Output is correct
25 Correct 147 ms 532 KB Output is correct
26 Correct 126 ms 512 KB Output is correct
27 Correct 140 ms 640 KB Output is correct
28 Correct 127 ms 760 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 9 ms 512 KB Output is correct
7 Correct 71 ms 512 KB Output is correct
8 Correct 89 ms 504 KB Output is correct
9 Correct 43 ms 384 KB Output is correct
10 Correct 92 ms 460 KB Output is correct
11 Correct 171 ms 516 KB Output is correct
12 Correct 57 ms 384 KB Output is correct
13 Correct 156 ms 512 KB Output is correct
14 Correct 152 ms 512 KB Output is correct
15 Correct 76 ms 504 KB Output is correct
16 Correct 50 ms 512 KB Output is correct
17 Correct 67 ms 512 KB Output is correct
18 Correct 62 ms 504 KB Output is correct
19 Correct 66 ms 508 KB Output is correct
20 Correct 56 ms 508 KB Output is correct
21 Correct 59 ms 504 KB Output is correct
22 Correct 52 ms 512 KB Output is correct
23 Correct 50 ms 504 KB Output is correct
24 Correct 145 ms 512 KB Output is correct
25 Correct 147 ms 532 KB Output is correct
26 Correct 126 ms 512 KB Output is correct
27 Correct 140 ms 640 KB Output is correct
28 Correct 127 ms 760 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 6 ms 1152 KB Output is correct
31 Correct 5437 ms 1912 KB Output is correct
32 Correct 3566 ms 1688 KB Output is correct
33 Correct 381 ms 1268 KB Output is correct
34 Execution timed out 8090 ms 1456 KB Time limit exceeded
35 Halted 0 ms 0 KB -