Submission #298714

#	Time	Username	Problem	Language	Result	Execution time	Memory
298714		eohomegrownapps	Sky Walking (IOI19_walk)	C++14	10 / 100	4025 ms	11792 KiB

walk

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

typedef long long ll;

//vector<pair<int,int>> adjlist[10000000]; // weight, node
vector<vector<pair<int,int>>> adjlist;
ll INF = 1e18;

ll dijkstra(int n, int a, int b){
    vector<ll> distance(n);
    for (int i = 0; i<n; i++){
        distance[i]=INF;
    }
    distance[a]=0;
    //priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    //pq.push({0,a});
    set<pair<ll,int>> pq;
    pq.insert({0,a});
    while (pq.size()>0){
        auto f = *pq.begin();
        pq.erase(pq.begin());
        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.insert({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;
    }

    vector<int> ind_order_height(n);
    for (int i = 0; i<n; i++){
        ind_order_height[i]=i;
        //hinds.insert(i);
    }
    set<int> hinds(ind_order_height.begin(),ind_order_height.end());
    sort(ind_order_height.begin(),ind_order_height.end(),[heights](int a, int b){return heights[a]<heights[b];});

    int curnode = n;
    int ptr = 0;
    for (int i = 0; i<m; i++){
        while (ptr<n&&heights[ind_order_height[ptr]]<y[inds[i]]){
            hinds.erase(ind_order_height[ptr]);
            ptr++;
        }
        // process skywalk inds[i]
        int lc = l[inds[i]];
        int rc = r[inds[i]];
        //cout<<"process "<<lc<<' '<<rc<<'\n';
        int prev = -1;
        auto it = hinds.lower_bound(lc);
        int lv = *it;
        while (it!=hinds.end()&&(*it)<=rc){
            int j = *it;
            //cout<<"heights: "<<heights[j]<<'\n';
            // link j to below
            
            if (heights[j]<y[inds[i]]){assert(1==0);}
            if (lastheight[j]!=y[inds[i]]){
                //cout<<"connect "<<curnode<<' '<<lastnode[j]<<'\n';
                adjlist.push_back(vector<pair<int,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!=lv){
                //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;
            it++;
        }
        //cout<<"bleh"<<endl;
    }
    if (n>50000){assert(1==0);}
    return dijkstra(curnode,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:51:9: warning: unused variable 'numnodes' [-Wunused-variable]
   51 |     int numnodes = 0;
      |         ^~~~~~~~

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