제출 #431890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431890		Pichon5	Sky Walking (IOI19_walk)	C++17	10 / 100	483 ms	149672 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=1e18;
const int tam=1000005;
vector<pair<int,int> > G[tam];
pair<int,int> E[tam];
long long min_distance(vi x,vi h,vi l, vi r,vi y,int s,int g){
    int n=x.size();
    int curr=0;
    int 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<int,int> >A;//altura e indice
    for(int i=0;i<l.size();i++)A.pb({y[i],i});
    sort(A.begin(),A.end());
    for(int i=0;i<l.size();i++){
        int ind=A[i].S;
        int equis;
        int ant=-1;
        for(int j=l[ind];j<=r[ind];j++){
            if(h[j]<y[ind])continue;
            G[curr].pb({E[j].F,y[ind]-E[j].S});
            G[E[j].F].pb({curr,y[ind]-E[j].S});
            //cout<<curr<<" "<<E[j].F<<"  =  "<<y[ind]-E[j].S<<endl;
            E[j]={curr,y[ind]};
            if(ant!=-1){
                G[curr].pb({ant,x[j]-equis});
                //cout<<curr<<"  "<<ant<<"  =  "<<x[j]-equis<<endl;
                G[ant].pb({curr,x[j]-equis});
            }
            ant=curr;
            equis=x[j];
            curr++;
        }
    }
    priority_queue<pair<int,int> >q;
    vll dis(1000006,INF);
    dis[entrada]=0;
    q.push({0,entrada});
    vector<bool>vis(1000006,false);
    while(!q.empty()){
        int nodo=q.top().S;
        q.pop();
        if(vis[nodo])continue;
        vis[nodo]=1;
        for(auto it : G[nodo]){
            int 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
*/

컴파일 시 표준 에러 (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:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<l.size();i++)A.pb({y[i],i});
      |                 ~^~~~~~~~~
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++){
      |                 ~^~~~~~~~~
walk.cpp:49:16: warning: 'entrada' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |     dis[entrada]=0;
      |                ^
walk.cpp:65:18: warning: 'salida' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     if(dis[salida]==INF)return -1;
      |                  ^

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