oj.uz

답안 #1036559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036559 2024-07-27T13:56:16 Z Abito Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 579256 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;
        ll D=dis[{x,y}];
        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}]>D+c[to]){
                    dis[{x,to}]=D+c[to];
                    pq.push({-dis[{x,to}],x,to});
                }
            }
            if (dis.find({x,m+1})==dis.end() || dis[{x,m+1}]>D+b[x]){
                dis[{x,m+1}]=D+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}]>D+b[x]-c[to]){
                    dis[{x,to}]=D+b[x]-c[to];
                    pq.push({-dis[{x,to}],x,to});
                }
            }
            if (dis.find({x,0})==dis.end() || dis[{x,0}]>D+b[x]){
                dis[{x,0}]=D+b[x];

            }continue;
        }
        if (dis.find({x,0})==dis.end() || dis[{x,0}]>D+c[y]){
            dis[{x,0}]=D+c[y];
            pq.push({-dis[{x,0}],x,0});
        }
        if (dis.find({x,m+1})==dis.end() || dis[{x,m+1}]>D+b[x]-c[y]){
            dis[{x,m+1}]=D+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}]>D+abs(c[to]-c[y])){
                dis[{x,to}]=D+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}]>D+abs(c[to]-c[y])){
                dis[{x,to}]=D+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}]>D+abs(a[to]-a[x])){
                dis[{to,y}]=D+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}]>D+abs(a[to]-a[x])){
                dis[{to,y}]=D+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 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 2 ms 14940 KB Output is correct
10 Correct 3 ms 15136 KB Output is correct
11 Correct 2 ms 14936 KB Output is correct
12 Correct 2 ms 14940 KB Output is correct
13 Correct 3 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 14936 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2548 ms 178184 KB Output is correct
4 Correct 1680 ms 204304 KB Output is correct
5 Correct 202 ms 80468 KB Output is correct
6 Correct 166 ms 72020 KB Output is correct
7 Correct 210 ms 80216 KB Output is correct
8 Correct 3494 ms 221880 KB Output is correct
9 Correct 424 ms 100436 KB Output is correct
10 Correct 2713 ms 272724 KB Output is correct
11 Correct 864 ms 111700 KB Output is correct
12 Correct 426 ms 99412 KB Output is correct
13 Correct 2143 ms 245588 KB Output is correct
14 Correct 115 ms 45396 KB Output is correct
15 Correct 608 ms 97168 KB Output is correct
16 Correct 530 ms 97468 KB Output is correct
17 Correct 499 ms 95060 KB Output is correct
18 Correct 720 ms 73640 KB Output is correct
19 Correct 21 ms 18772 KB Output is correct
20 Correct 250 ms 54024 KB Output is correct
21 Correct 339 ms 89684 KB Output is correct
22 Correct 678 ms 98552 KB Output is correct
23 Correct 844 ms 112960 KB Output is correct
24 Correct 540 ms 97104 KB Output is correct
25 Correct 440 ms 94804 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 44880 KB Output is correct
2 Execution timed out 4034 ms 579256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 44880 KB Output is correct
2 Execution timed out 4034 ms 579256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 2 ms 14940 KB Output is correct
10 Correct 3 ms 15136 KB Output is correct
11 Correct 2 ms 14936 KB Output is correct
12 Correct 2 ms 14940 KB Output is correct
13 Correct 3 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 14936 KB Output is correct
18 Correct 2 ms 14936 KB Output is correct
19 Correct 2 ms 14940 KB Output is correct
20 Correct 2548 ms 178184 KB Output is correct
21 Correct 1680 ms 204304 KB Output is correct
22 Correct 202 ms 80468 KB Output is correct
23 Correct 166 ms 72020 KB Output is correct
24 Correct 210 ms 80216 KB Output is correct
25 Correct 3494 ms 221880 KB Output is correct
26 Correct 424 ms 100436 KB Output is correct
27 Correct 2713 ms 272724 KB Output is correct
28 Correct 864 ms 111700 KB Output is correct
29 Correct 426 ms 99412 KB Output is correct
30 Correct 2143 ms 245588 KB Output is correct
31 Correct 115 ms 45396 KB Output is correct
32 Correct 608 ms 97168 KB Output is correct
33 Correct 530 ms 97468 KB Output is correct
34 Correct 499 ms 95060 KB Output is correct
35 Correct 720 ms 73640 KB Output is correct
36 Correct 21 ms 18772 KB Output is correct
37 Correct 250 ms 54024 KB Output is correct
38 Correct 339 ms 89684 KB Output is correct
39 Correct 678 ms 98552 KB Output is correct
40 Correct 844 ms 112960 KB Output is correct
41 Correct 540 ms 97104 KB Output is correct
42 Correct 440 ms 94804 KB Output is correct
43 Correct 190 ms 44880 KB Output is correct
44 Execution timed out 4034 ms 579256 KB Time limit exceeded
45 Halted 0 ms 0 KB -