제출 #294149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294149		tqbfjotld	Sky Walking (IOI19_walk)	C++14	24 / 100	1199 ms	195184 KiB

walk

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

vector<pair<pair<int,int>,int> > v;
vector<pair<int,long long> > adjl[1100005];
long long dist[1100005];
vector<pair<int,int> > skyh[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) {
    vector<pair<int,int> > news;
    for (int x = 0; x<X.size(); x++){
        news.push_back({h[x],x});
    }
    sort(news.begin(),news.end(),greater<pair<int,int> >());
    set<int> S;
    vector<pair<int,int> > sky;
    for (int x = 0; x<l.size(); x++){
        sky.push_back({y[x],x});
    }
    int nwn = X.size();
    sort(sky.begin(),sky.end(),greater<pair<int,int> >());
    int cur = 0;
    for (auto x : sky){
        while (cur!=X.size() && news[cur].first>=x.first){
            S.insert(news[cur].second);
            cur++;
        }
        bool isn = true;
        int pre = -1;
        for (auto it = S.lower_bound(l[x.second]); it!=S.end() && (*it)<=r[x.second]; it++){
            int nw = nwn++;
            //printf("%d is (%d,%d)\n",nw,X[(*it)],x.first);
            skyh[(*it)].push_back({x.first,nw});
            if (!isn){
                adjl[nw].push_back({nw-1,X[(*it)]-pre});
                adjl[nw-1].push_back({nw,X[(*it)]-pre});
                //printf("add edge %d %d %d\n",nw,nw-1,X[(*it)]-pre);
            }
            pre = X[(*it)];
            isn = false;
        }
    }
    int stn,endn;
    for (int x = 0; x<X.size(); x++){
        if (x==s){
            stn = nwn++;
            skyh[x].push_back({0,stn});
        }
        if (x==g){
            endn = nwn++;
            skyh[x].push_back({0,endn});
        }
        sort(skyh[x].begin(),skyh[x].end());
        for (int z = 1; z<skyh[x].size(); z++){
            adjl[skyh[x][z].second].push_back({skyh[x][z-1].second,skyh[x][z].first-skyh[x][z-1].first});
            adjl[skyh[x][z-1].second].push_back({skyh[x][z].second,skyh[x][z].first-skyh[x][z-1].first});
            //printf("add edge %d-%d,%d\n",skyh[x][z-1].second,skyh[x][z].second,skyh[x][z].first-skyh[x][z-1].first);
        }
    }
    //printf("stn,%d,endn,%d\n",stn,endn);
    priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >pq;
    memset(dist,-1,sizeof(dist));
    dist[stn] = 0;
    pq.push({0,stn});
    while (!pq.empty()){
        int nd = pq.top().second;
        long long 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});
            }
        }
    }
    if (dist[endn]==-1) return -1;
    //printf("distThing = %d\n",dist[endn]);
	return dist[endn];
}

컴파일 시 표준 에러 (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:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int x = 0; x<X.size(); x++){
      |                     ~^~~~~~~~~
walk.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int x = 0; x<l.size(); x++){
      |                     ~^~~~~~~~~
walk.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         while (cur!=X.size() && news[cur].first>=x.first){
      |                ~~~^~~~~~~~~~
walk.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int x = 0; x<X.size(); x++){
      |                     ~^~~~~~~~~
walk.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int z = 1; z<skyh[x].size(); z++){
      |                         ~^~~~~~~~~~~~~~~
walk.cpp:80:18: warning: 'endn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |     if (dist[endn]==-1) return -1;
      |         ~~~~~~~~~^

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