Submission #298692

#	Time	Username	Problem	Language	Result	Execution time	Memory
298692		eohomegrownapps	Sky Walking (IOI19_walk)	C++14	10 / 100	4064 ms	13772 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<vector<pair<ll,int>>> adjlist; // weight, node

ll INF = 1e18;

ll dijkstra(int a, int b){
    int n = adjlist.size();
    vector<ll> distance(n,INF);
    distance[a]=0;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0,a});
    while (pq.size()>0){
        auto f = pq.top();
        pq.pop();
        if (f.first>distance[f.second]){continue;}
        for (auto p : adjlist[f.second]){
            if (distance[f.second]+p.first<distance[p.second]){
                distance[p.second]=distance[f.second]+p.first;
                pq.push({distance[p.second],p.second});
            }
        }
    }
    return (distance[b]==INF)?-1:distance[b];
}

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	// x - horizontal distance
    int n = x.size();
    vector<int> coords = x;
    sort(coords.begin(),coords.end());
    vector<int> heights(n);
    for (int i = 0; i<n; i++){
        heights[i]=h[lower_bound(coords.begin(),coords.end(),x[i])-coords.begin()];
    }
    int m = l.size();
    vector<int> inds(m);
    for (int i = 0; i<m; i++){
        inds[i]=i;
    }
    sort(inds.begin(),inds.end(),[y](int a, int b){return y[a]<y[b];});
    int numnodes = 0;
    vector<int> lastnode(n);
    vector<int> lastheight(n,0);
    adjlist.resize(n);
    for (int i = 0; i<n; i++){
        lastnode[i]=i;
    }

    int curnode = n;
    for (int i = 0; i<m; i++){
        // process skywalk inds[i]
        int lc = l[inds[i]];
        int rc = r[inds[i]];
        //cout<<"process "<<lc<<' '<<rc<<'\n';
        int prev = -1;
        for (int j = lc; j<=rc; j++){
            //cout<<"heights: "<<heights[j]<<'\n';
            // link j to below
            if (heights[j]<y[inds[i]]){continue;}
            if (lastheight[j]!=y[inds[i]]){
                //cout<<"connect "<<curnode<<' '<<lastnode[j]<<'\n';
                adjlist.push_back(vector<pair<ll,int>>());
                adjlist[curnode].push_back({y[inds[i]]-lastheight[j],lastnode[j]});
                adjlist[lastnode[j]].push_back({y[inds[i]]-lastheight[j],curnode});
                lastnode[j]=curnode;
                lastheight[j]=y[inds[i]];
                curnode++;
            }
            // link j to left
            if (j!=lc){
                //cout<<"connect "<<lastnode[j]<<' '<<lastnode[prev]<<'\n';
                adjlist[lastnode[j]].push_back({x[j]-x[prev],lastnode[prev]});
                adjlist[lastnode[prev]].push_back({x[j]-x[prev],lastnode[j]});
            }
            prev = j;
        }
    }
    return dijkstra(s,g);
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:46:9: warning: unused variable 'numnodes' [-Wunused-variable]
   46 |     int numnodes = 0;
      |         ^~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43