Submission #431908

#	Time	Username	Problem	Language	Result	Execution time	Memory
431908		Pichon5	Sky Walking (IOI19_walk)	C++17	24 / 100	860 ms	453276 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
using namespace std;
const ll INF=2ll*1e18;
const int tam=2000005;
vector<pair<ll,ll> > G[tam];
pair<ll,ll> E[tam];
vector<bool>vis(tam,false);
vll dis(tam,INF);
long long min_distance(vi x,vi h,vi l, vi r,vi y,int s,int g){
    ll n=x.size();
    ll curr=0;
    ll entrada,salida;
    for(int i=0;i<n;i++){
        E[i]={curr,0};
        if(i==s)entrada=curr;
        if(i==g)salida=curr;
        curr++;
    }
    vector<pair<ll,ll> >A;//altura e indice
    for(int i=0;i<l.size();i++)A.pb({y[i],i});
    sort(A.begin(),A.end());
    set<ll>st;
    for(int i=0;i<n;i++)st.insert(i);
    for(int i=0;i<l.size();i++){
        ll ind=A[i].S;
        ll equis;
        ll ant=-1;
        vll AUX;
        for(auto it=st.lower_bound(l[ind]);it!=st.end() && *it<=r[ind];it++){
            ll j=*it;
            if(h[j]<y[ind]){
                AUX.pb(j);
                continue;
            }
            G[curr].pb({E[j].F,y[ind]-E[j].S});
            G[E[j].F].pb({curr,y[ind]-E[j].S});
            E[j]={curr,y[ind]};
            if(ant!=-1){
                G[curr].pb({ant,x[j]-equis});
                G[ant].pb({curr,x[j]-equis});
            }
            ant=curr;
            equis=x[j];
            curr++;
        }
        for(int k=0;k<AUX.size();k++){
            auto I=st.find(AUX[k]);
            st.erase(I);
        }
    }
    priority_queue<pair<ll,ll> >q;
    dis[entrada]=0ll;
    q.push({0ll,entrada});
    while(!q.empty()){
        ll nodo=q.top().S;
        q.pop();
        if(vis[nodo])continue;
        vis[nodo]=1;
        for(auto it : G[nodo]){
            ll to=it.F,w=it.S;
            if(dis[nodo]+w<dis[to]){
                dis[to]=dis[nodo]+w;
                q.push({-dis[to],to});
            }
        }
    }
    if(dis[salida]==INF)return -1;
    return dis[salida];
}
/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
*/

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:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<l.size();i++)A.pb({y[i],i});
      |                 ~^~~~~~~~~
walk.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i<l.size();i++){
      |                 ~^~~~~~~~~
walk.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int k=0;k<AUX.size();k++){
      |                     ~^~~~~~~~~~~
walk.cpp:47:37: warning: 'equis' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |                 G[ant].pb({curr,x[j]-equis});
walk.cpp:59:16: warning: 'entrada' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     dis[entrada]=0ll;
      |                ^
walk.cpp:74:18: warning: 'salida' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     if(dis[salida]==INF)return -1;
      |                  ^

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