oj.uz

Submission #778558

# Submission time Handle Problem Language Result Execution time Memory
778558 2023-07-10T12:15:32 Z jasmin Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 502832 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;

const long long INF=1e18;

int distance(int i, int h, int j, int h2, vector<int>& x){
    return abs(x[i]-x[j]) + abs(h-h2);
}

long long dijkstra(int n, unordered_map<int, unordered_map<int, vector<pair<int,int> > > >& adi, int a, int b, vector<int>& x){

    unordered_map<int, unordered_map<int, long long> > dist; //plus 1
    dist[a][0]=1;

    unordered_map<int, unordered_map<int, bool> > vis;

    priority_queue<pair<long long, pair<int,int> > > pq;
    pq.push({-1, {a, 0}});
    while(!pq.empty()){
        auto [v, h] = pq.top().second;
        pq.pop();

        if(vis[v][h]) continue;
        vis[v][h]=true;

        for(auto [u, h2]: adi[v][h]){

            if(dist[u][h2]==0 || dist[v][h]+distance(v, h, u, h2, x)<dist[u][h2]){

                dist[u][h2] = dist[v][h] + distance(v, h, u, h2, x);
                pq.push({-dist[u][h2], {u, h2}});
            }
        }

    }

    return dist[b][0]-1;
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
    int n=x.size();
    int m=l.size();

    //compressing skywalks
    /*map<int, vector<pair<int,int> > > sw;
    for(int i=0; i<m; i++){
        sw[ yinit[i] ].push_back({linit[i], rinit[i]});
    }

    vector<int> l;
    vector<int> r;
    vector<int> y;
    for(auto [hi, vec]: sw){

        pair<int,int> last={-1, -1};
        for(auto [left, right]: vec){

            if(last.second==left){
                last.second=right;
            }
            else{
                l.push_back(last.first);
                r.push_back(last.second);
                y.push_back(hi);

                last={left, right};
            }

        }

        l.push_back(last.first);
        r.push_back(last.second);
        y.push_back(hi);
    }
    m=l.size();*/


    //build graph

    vector<int> sorth(n, 0);
    iota(sorth.begin(), sorth.end(), 0);
    sort(sorth.begin(), sorth.end(), [&](int i, int j){
        return h[i]<h[j];
    });

    vector<int> sorty(m, 0);
    iota(sorty.begin(), sorty.end(), 0);
    sort(sorty.begin(), sorty.end(), [&](int i, int j){
        return y[i]<y[j];
    });

    set<pair<int, int> > active;
    for(int i=0; i<n; i++){
        active.insert({x[i], i});
    }

    int j=0;
    unordered_map<int, unordered_map<int, vector<pair<int,int> > > > adi;
    vector<set<int> > hights(n, {0});

    for(auto i: sorty){
        while(j<n && h[sorth[j]] < y[i]){
            active.erase({x[sorth[j]], sorth[j]});
            j++;
        }

        auto p = active.lower_bound({x[l[i]], 0});
        while(next(p)!=active.end() && (*next(p)).first<=x[r[i]]){

            //horizontal conection

            int ind=(*p).second;
            int ind2=(*next(p)).second;

            adi[ind][y[i]].push_back({ind2, y[i]}); hights[ind].insert(y[i]);
            adi[ind2][y[i]].push_back({ind, y[i]}); hights[ind2].insert(y[i]);

            p=next(p);
        }
    }

    for(int i=0; i<n; i++){
        int last=*hights[i].begin();

        for(auto e: hights[i]){
            if(e==last) continue;

            adi[i][last].push_back({i, e});
            adi[i][e].push_back({i, last});

            last=e;
        }
    }

    return dijkstra(n, adi, s, g, x);
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> x(n);
    vector<int> h(n);
    for(int i=0; i<n; i++){
        cin >> x[i];
    }
    for(int i=0; i<n; i++){
        cin >> h[i];
    }

    vector<int> l(m);
    vector<int> r(m);
    vector<int> y(m);
    for(int i=0; i<m; i++){
        cin >> l[i];
    }
    for(int i=0; i<m; i++){
        cin >> r[i];
    }
    for(int i=0; i<m; i++){
        cin >> y[i];
    }

    int s, g;
    cin >> s >> g;

    cout << min_distance(x, h, l, r, y, s, g) << "\n";
}*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 428 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2446 ms 177972 KB Output is correct
4 Correct 1746 ms 231396 KB Output is correct
5 Correct 784 ms 141160 KB Output is correct
6 Correct 703 ms 127036 KB Output is correct
7 Correct 818 ms 141204 KB Output is correct
8 Correct 3270 ms 223376 KB Output is correct
9 Correct 1076 ms 140276 KB Output is correct
10 Correct 2703 ms 303796 KB Output is correct
11 Correct 963 ms 110632 KB Output is correct
12 Correct 748 ms 128436 KB Output is correct
13 Correct 2023 ms 264956 KB Output is correct
14 Correct 361 ms 67008 KB Output is correct
15 Correct 655 ms 128268 KB Output is correct
16 Correct 655 ms 123240 KB Output is correct
17 Correct 648 ms 119800 KB Output is correct
18 Correct 354 ms 65156 KB Output is correct
19 Correct 15 ms 6436 KB Output is correct
20 Correct 213 ms 61876 KB Output is correct
21 Correct 581 ms 108436 KB Output is correct
22 Correct 729 ms 128220 KB Output is correct
23 Correct 707 ms 141632 KB Output is correct
24 Correct 672 ms 124096 KB Output is correct
25 Correct 685 ms 119504 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 22860 KB Output is correct
2 Execution timed out 4074 ms 502832 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 22860 KB Output is correct
2 Execution timed out 4074 ms 502832 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 428 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 2446 ms 177972 KB Output is correct
21 Correct 1746 ms 231396 KB Output is correct
22 Correct 784 ms 141160 KB Output is correct
23 Correct 703 ms 127036 KB Output is correct
24 Correct 818 ms 141204 KB Output is correct
25 Correct 3270 ms 223376 KB Output is correct
26 Correct 1076 ms 140276 KB Output is correct
27 Correct 2703 ms 303796 KB Output is correct
28 Correct 963 ms 110632 KB Output is correct
29 Correct 748 ms 128436 KB Output is correct
30 Correct 2023 ms 264956 KB Output is correct
31 Correct 361 ms 67008 KB Output is correct
32 Correct 655 ms 128268 KB Output is correct
33 Correct 655 ms 123240 KB Output is correct
34 Correct 648 ms 119800 KB Output is correct
35 Correct 354 ms 65156 KB Output is correct
36 Correct 15 ms 6436 KB Output is correct
37 Correct 213 ms 61876 KB Output is correct
38 Correct 581 ms 108436 KB Output is correct
39 Correct 729 ms 128220 KB Output is correct
40 Correct 707 ms 141632 KB Output is correct
41 Correct 672 ms 124096 KB Output is correct
42 Correct 685 ms 119504 KB Output is correct
43 Correct 97 ms 22860 KB Output is correct
44 Execution timed out 4074 ms 502832 KB Time limit exceeded
45 Halted 0 ms 0 KB -