oj.uz

Submission #1036465

# Submission time Handle Problem Language Result Execution time Memory
1036465 2024-07-27T11:56:40 Z Abito Sky Walking (IOI19_walk) C++17
10 / 100
 20 ms 7592 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define int long long
#define ep insert
using namespace std;
const int N=55;
int n,m,a[N],b[N],L[N],R[N],c[N],dis[N][N];
set<pair<int,int>> s[2][N];
bool vis[N][N];
void dijkstra(int src){
    for (int i=1;i<=n;i++) for (int j=0;j<=m+1;j++) dis[i][j]=LLONG_MAX;
    dis[src][0]=0;
    priority_queue<vector<int>> pq;
    pq.push({0,src,0});
    while (!pq.empty()){
        int x=pq.top()[1],y=pq.top()[2];
        pq.pop();
        if (vis[x][y]) continue;
        vis[x][y]=1;
        if (y==0){
            if (!s[0][x].empty()){
                int to=(*s[0][x].begin()).S;
                if (dis[x][to]>dis[x][y]+c[to]){
                    dis[x][to]=dis[x][y]+c[to];
                    pq.push({-dis[x][to],x,to});
                }
            }
            if (dis[x][m+1]>dis[x][y]+b[x]){
                dis[x][m+1]=dis[x][y]+b[x];
                pq.push({-dis[x][m+1],x,m+1});
            }
            continue;
        }
        if (y==m+1){
            if (!s[0][x].empty()){
                int to=(*--s[0][x].end()).S;
                if (dis[x][to]>dis[x][y]+b[x]-c[to]){
                    dis[x][to]=dis[x][y]+b[x]-c[to];
                    pq.push({-dis[x][to],x,to});
                }
            }
            if (dis[x][0]>dis[x][y]+b[x]){
                dis[x][0]=dis[x][y]+b[x];

            }continue;
        }
        if (dis[x][0]>dis[x][y]+c[y]){
            dis[x][0]=dis[x][y]+c[y];
            pq.push({-dis[x][0],x,0});
        }
        if (dis[x][m+1]>dis[x][y]+b[x]-c[y]){
            dis[x][m+1]=dis[x][y]+b[x]-c[y];
            pq.push({-dis[x][m+1],x,m+1});
        }
        auto it=s[0][x].upper_bound({c[y],y});
        if (it!=s[0][x].end()){
            int to=(*it).S;
            if (dis[x][to]>dis[x][y]+abs(c[to]-c[y])){
                dis[x][to]=dis[x][y]+abs(c[to]-c[y]);
                pq.push({-dis[x][to],x,to});
            }
        }
        it=s[0][x].lower_bound({c[y],y});
        if (it!=s[0][x].begin()){
            int to=(*--it).S;
            if (dis[x][to]>dis[x][y]+abs(c[to]-c[y])){
                dis[x][to]=dis[x][y]+abs(c[to]-c[y]);
                pq.push({-dis[x][to],x,to});
            }
        }
        it=s[1][y].upper_bound({a[x],x});
        if (it!=s[1][y].end()){
            int to=(*it).S;
            if (dis[to][y]>dis[x][y]+abs(a[to]-a[x])){
                dis[to][y]=dis[x][y]+abs(a[to]-a[x]);
                pq.push({-dis[to][y],to,y});
            }
        }
        it=s[1][y].lower_bound({a[x],x});
        if (it!=s[1][y].begin()){
            int to=(*--it).S;
            if (dis[to][y]>dis[x][y]+abs(a[to]-a[x])){
                dis[to][y]=dis[x][y]+abs(a[to]-a[x]);
                pq.push({-dis[to][y],to,y});
            }
        }
    }return;
}
long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t S, int32_t g) {
    n=x.size(),m=l.size();
    for (int i=0;i<n;i++) a[i+1]=x[i],b[i+1]=h[i];
    for (int j=0;j<m;j++) L[j+1]=l[j]+1,R[j+1]=r[j]+1,c[j+1]=y[j];
    for (int j=1;j<=m;j++){
        for (int i=L[j];i<=R[j];i++){
            if (b[i]<c[j]) continue;
            s[0][i].ep({c[j],j});
            s[1][j].ep({a[i],i});
        }
    }
    dijkstra(S+1);
    if (dis[g+1][0]==LLONG_MAX) return -1;
    return dis[g+1][0];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 20 ms 7592 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 3676 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 3676 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Runtime error 20 ms 7592 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -