oj.uz

답안 #1036526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036526 2024-07-27T13:31:31 Z Abito Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 710020 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=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>,int> dis,vis;
vector<pair<int,int>> ad[N],er[N];
void dijkstra(int src){
    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;
        //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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17012 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 5 ms 16984 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 4 ms 17244 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 4 ms 17016 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 3 ms 16984 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 6 ms 17012 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3952 ms 204432 KB Output is correct
4 Correct 2251 ms 232672 KB Output is correct
5 Correct 294 ms 104864 KB Output is correct
6 Correct 225 ms 94708 KB Output is correct
7 Correct 248 ms 105332 KB Output is correct
8 Execution timed out 4096 ms 240984 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 51212 KB Output is correct
2 Execution timed out 4137 ms 710020 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 51212 KB Output is correct
2 Execution timed out 4137 ms 710020 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17012 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 5 ms 16984 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 4 ms 17244 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 4 ms 17016 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 3 ms 16984 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 6 ms 17012 KB Output is correct
18 Correct 5 ms 16984 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 3952 ms 204432 KB Output is correct
21 Correct 2251 ms 232672 KB Output is correct
22 Correct 294 ms 104864 KB Output is correct
23 Correct 225 ms 94708 KB Output is correct
24 Correct 248 ms 105332 KB Output is correct
25 Execution timed out 4096 ms 240984 KB Time limit exceeded
26 Halted 0 ms 0 KB -