oj.uz

Submission #778524

# Submission time Handle Problem Language Result Execution time Memory
778524 2023-07-10T11:42:23 Z jasmin Sky Walking (IOI19_walk) C++17
0 / 100
 15 ms 3916 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, map<int, map<int, vector<pair<int,int> > > >& adi, int a, int b, vector<int>& x){

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

    map<int, 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);
            }
        }

    }

    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();

    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;
    map<int, 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({l[i], 0});
        while(next(p)!=active.end() && (*next(p)).first<=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);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 3916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 3916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -