oj.uz

Submission #1036531

# Submission time Handle Problem Language Result Execution time Memory
1036531 2024-07-27T13:34:51 Z Abito Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 570204 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define ll long long
//#define int long long
#define ep insert
using namespace std;
const int N=1e5+5;
int n,m,a[N],b[N],L[N],R[N],c[N];
set<pair<int,int>> s[2][N];
map<pair<int,int>,ll> dis;
map<pair<int,int>,bool> vis;
vector<pair<int,int>> ad[N],er[N];
void dijkstra(int src){
    dis[{src,0}]=0;
    priority_queue<vector<ll>> 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;
        //cout<<x<<' '<<y<<endl;
        vis[{x,y}]=1;
        if (y==0){
            if (!s[0][x].empty()){
                int to=(*s[0][x].begin()).S;
                if (dis.find({x,to})==dis.end() || 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.find({x,m+1})==dis.end() || 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.find({x,to})==dis.end() || 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.find({x,0})==dis.end() || dis[{x,0}]>dis[{x,y}]+b[x]){
                dis[{x,0}]=dis[{x,y}]+b[x];

            }continue;
        }
        if (dis.find({x,0})==dis.end() || 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.find({x,m+1})==dis.end() || 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.find({x,to})==dis.end() || 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.find({x,to})==dis.end() || 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.find({to,y})==dis.end() || 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.find({to,y})==dis.end() || 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++){
        ad[L[j]].pb({c[j],j});
        er[R[j]].pb({c[j],j});
    }
    set<pair<int,int>> ms;
    for (int i=1;i<=n;i++){
        for (auto u:ad[i]) ms.ep(u);
        for (auto u:ms){
            if (u.F<=b[i]) s[0][i].ep(u),s[1][u.S].ep({a[i],i});
            else break;
        }
        for (auto u:er[i]) ms.erase(u);
    }
    dijkstra(S+1);
    if (dis.find({g+1,0})==dis.end()) return -1;
    return dis[{g+1,0}];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 15096 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 14956 KB Output is correct
6 Correct 3 ms 15192 KB Output is correct
7 Correct 4 ms 15044 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14936 KB Output is correct
10 Correct 4 ms 14944 KB Output is correct
11 Correct 2 ms 14940 KB Output is correct
12 Correct 2 ms 14936 KB Output is correct
13 Correct 2 ms 14940 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 2 ms 14940 KB Output is correct
16 Correct 2 ms 14940 KB Output is correct
17 Correct 4 ms 14940 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2804 ms 180272 KB Output is correct
4 Correct 1861 ms 208276 KB Output is correct
5 Correct 209 ms 82664 KB Output is correct
6 Correct 177 ms 73968 KB Output is correct
7 Correct 199 ms 82256 KB Output is correct
8 Execution timed out 4050 ms 222072 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 44368 KB Output is correct
2 Execution timed out 4093 ms 570204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 44368 KB Output is correct
2 Execution timed out 4093 ms 570204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 15096 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 14956 KB Output is correct
6 Correct 3 ms 15192 KB Output is correct
7 Correct 4 ms 15044 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14936 KB Output is correct
10 Correct 4 ms 14944 KB Output is correct
11 Correct 2 ms 14940 KB Output is correct
12 Correct 2 ms 14936 KB Output is correct
13 Correct 2 ms 14940 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 2 ms 14940 KB Output is correct
16 Correct 2 ms 14940 KB Output is correct
17 Correct 4 ms 14940 KB Output is correct
18 Correct 2 ms 14940 KB Output is correct
19 Correct 2 ms 14940 KB Output is correct
20 Correct 2804 ms 180272 KB Output is correct
21 Correct 1861 ms 208276 KB Output is correct
22 Correct 209 ms 82664 KB Output is correct
23 Correct 177 ms 73968 KB Output is correct
24 Correct 199 ms 82256 KB Output is correct
25 Execution timed out 4050 ms 222072 KB Time limit exceeded
26 Halted 0 ms 0 KB -