Submission #293866

#	Time	Username	Problem	Language	Result	Execution time	Memory
293866		tqbfjotld	Sky Walking (IOI19_walk)	C++14	0 / 100	67 ms	8816 KiB

walk

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

vector<pair<pair<int,int>,int> > v;
vector<pair<int,int> > adjl[100005];
int dist[100005];

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) {
    for (int x = 0; x<l.size(); x++){
        v.push_back({{l[x],0},x});
        v.push_back({{r[x],1},x});
    }
    sort(v.begin(),v.end());
    set<pair<int,int> > S;
    int stn = l.size();
    int endn = l.size()+1;
    for (auto x : v){
        if (x.first.second==0){
            auto it = S.lower_bound({y[x.second],x.second});
            if (it!=S.end()){
                adjl[x.second].push_back({(*it).second,abs(y[x.second]-y[(*it).second])});
                adjl[(*it).second].push_back({x.second,abs(y[x.second]-y[(*it).second])});
                //printf("add edge %d-%d, %d\n",x.second,(*it).second,abs(y[x.second]-y[(*it).second]));
            }
            if (it!=S.begin()){
                it--;
                adjl[x.second].push_back({(*it).second,abs(y[x.second]-y[(*it).second])});
                adjl[(*it).second].push_back({x.second,abs(y[x.second]-y[(*it).second])});
                //printf("Add edge %d-%d, %d\n",x.second,(*it).second,abs(y[x.second]-y[(*it).second]));
            }
            S.insert({y[x.second],x.second});
        }
        else{
            auto it = S.lower_bound({y[x.second],x.second});
            S.erase(it);
        }
        if (x.first.first==0 && x.first.second==0){
            adjl[stn].push_back({x.second,y[x.second]});
        }
        if (x.first.first==(int)l.size()-1 && x.first.second==1){
            adjl[x.second].push_back({endn,y[x.second]});
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
    memset(dist,-1,sizeof(dist));
    dist[stn] = 0;
    pq.push({0,stn});
    while (!pq.empty()){
        int nd = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d>dist[nd]) continue;
        //printf("d[%d] = %d\n",nd,d);
        for (auto x : adjl[nd]){
            if (dist[x.first]==-1 || d+x.second<dist[x.first]){
                dist[x.first] = d+x.second;
                pq.push({dist[x.first],x.first});
            }
        }
    }
    //printf("distThing = %d\n",dist[endn]);
	return dist[endn] + *X.begin()+ (*--X.end());
}

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:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int x = 0; x<l.size(); x++){
      |                     ~^~~~~~~~~

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