oj.uz

Submission #257328

# Submission time Handle Problem Language Result Execution time Memory
257328 2020-08-04T06:11:24 Z 최은수(#5045) None (JOI16_skating) C++17
100 / 100
 704 ms 123256 KB 
#include<iostream>
#include<vector>
#include<queue>
#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;
char map[1010][1010];
int l[1010][1010],r[1010][1010],u[1010][1010],d[1010][1010];
int dis[1000010];
vector<pi>adj[1000010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    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;)
        for(int j=0;j++<m;)
            l[i][j]=map[i][j-1]=='.'?l[i][j-1]:j,u[i][j]=map[i-1][j]=='.'?u[i-1][j]:i;
    for(int i=n;i>0;i--)
        for(int j=m;j>0;j--)
            r[i][j]=map[i][j+1]=='.'?r[i][j+1]:j,d[i][j]=map[i+1][j]=='.'?d[i+1][j]:i;
    for(int i=0;i++<n;)
    {
        for(int j=0;j++<m;)
        {
            if(map[i][j]!='.')
                continue;
            int cur=(i-1)*m+(j-1);
            for(int k=-2;k<2;k++)
            {
                int nx=i+k%2;
                int ny=j+(k+1)%2;
                int nxt=(nx-1)*m+(ny-1);
                if(map[nx][ny]=='.')
                    adj[cur].eb(nxt,2);
            }
            if(l[i][j]!=j)
                adj[cur].eb((i-1)*m+(l[i][j]-1),1);
            if(r[i][j]!=j)
                adj[cur].eb((i-1)*m+(r[i][j]-1),1);
            if(u[i][j]!=i)
                adj[cur].eb((u[i][j]-1)*m+(j-1),1);
            if(d[i][j]!=i)
                adj[cur].eb((d[i][j]-1)*m+(j-1),1);
        }
    }
    fill(dis,dis+n*m,inf);
    priority_queue<pi,vector<pi>,greater<pi> >pq;
    int sx,sy,ex,ey;
    cin>>sx>>sy;
    cin>>ex>>ey;
    pq.ep(dis[(sx-1)*m+(sy-1)]=0,(sx-1)*m+(sy-1));
    while(!pq.empty())
    {
        int i=pq.top().se;
        int d=pq.top().fi;
        pq.pop();
        for(pi&t:adj[i])
            if(dis[t.fi]>d+t.se)
                pq.ep(dis[t.fi]=d+t.se,t.fi);
    }
    int r=dis[(ex-1)*m+(ey-1)];
    if(r==inf)
        r=-1;
    cout<<r<<endl;
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 16 ms 24064 KB Output is correct
3 Correct 15 ms 24064 KB Output is correct
4 Correct 20 ms 24064 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 20 ms 24008 KB Output is correct
7 Correct 16 ms 24064 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 15 ms 24064 KB Output is correct
10 Correct 15 ms 24064 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 16 ms 24064 KB Output is correct
3 Correct 15 ms 24064 KB Output is correct
4 Correct 20 ms 24064 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 20 ms 24008 KB Output is correct
7 Correct 16 ms 24064 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 15 ms 24064 KB Output is correct
10 Correct 15 ms 24064 KB Output is correct
11 Correct 36 ms 30456 KB Output is correct
12 Correct 33 ms 30460 KB Output is correct
13 Correct 33 ms 30464 KB Output is correct
14 Correct 29 ms 29432 KB Output is correct
15 Correct 22 ms 28288 KB Output is correct
16 Correct 33 ms 30464 KB Output is correct
17 Correct 30 ms 29568 KB Output is correct
18 Correct 27 ms 29176 KB Output is correct
19 Correct 30 ms 29688 KB Output is correct
20 Correct 35 ms 30200 KB Output is correct
21 Correct 24 ms 28672 KB Output is correct
22 Correct 20 ms 28032 KB Output is correct
23 Correct 31 ms 29184 KB Output is correct
24 Correct 32 ms 30200 KB Output is correct
25 Correct 28 ms 29056 KB Output is correct
26 Correct 31 ms 28928 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 16 ms 24064 KB Output is correct
3 Correct 15 ms 24064 KB Output is correct
4 Correct 20 ms 24064 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 20 ms 24008 KB Output is correct
7 Correct 16 ms 24064 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 15 ms 24064 KB Output is correct
10 Correct 15 ms 24064 KB Output is correct
11 Correct 36 ms 30456 KB Output is correct
12 Correct 33 ms 30460 KB Output is correct
13 Correct 33 ms 30464 KB Output is correct
14 Correct 29 ms 29432 KB Output is correct
15 Correct 22 ms 28288 KB Output is correct
16 Correct 33 ms 30464 KB Output is correct
17 Correct 30 ms 29568 KB Output is correct
18 Correct 27 ms 29176 KB Output is correct
19 Correct 30 ms 29688 KB Output is correct
20 Correct 35 ms 30200 KB Output is correct
21 Correct 24 ms 28672 KB Output is correct
22 Correct 20 ms 28032 KB Output is correct
23 Correct 31 ms 29184 KB Output is correct
24 Correct 32 ms 30200 KB Output is correct
25 Correct 28 ms 29056 KB Output is correct
26 Correct 31 ms 28928 KB Output is correct
27 Correct 598 ms 122884 KB Output is correct
28 Correct 674 ms 123256 KB Output is correct
29 Correct 646 ms 123120 KB Output is correct
30 Correct 492 ms 113784 KB Output is correct
31 Correct 164 ms 69368 KB Output is correct
32 Correct 552 ms 122872 KB Output is correct
33 Correct 114 ms 48504 KB Output is correct
34 Correct 317 ms 107640 KB Output is correct
35 Correct 480 ms 120952 KB Output is correct
36 Correct 382 ms 108920 KB Output is correct
37 Correct 254 ms 90232 KB Output is correct
38 Correct 704 ms 122484 KB Output is correct
39 Correct 240 ms 75896 KB Output is correct
40 Correct 104 ms 60408 KB Output is correct