제출 #1036489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036489		Abito	Sky Walking (IOI19_walk)	C++17	0 / 100	2324 ms	308352 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define int long long
#define ep insert
#define elif else if
using namespace std;
const int N=1e5+5;
int n,m,a[N],b[N],L[N],R[N],c[N],dis[N][15];
vector<pair<int,int>> ad[N],er[N];
vector<int> v[N];
set<int> s[N];
bool vis[N][15];
void dijkstra(int src){
    for (int i=1;i<=n;i++) for (int j=0;j<15;j++) dis[i][j]=LLONG_MAX;
    dis[src][11]=0;
    priority_queue<vector<int>> pq;
    pq.push({0,src,11});
    while (!pq.empty()){
        int x=pq.top()[1],y=pq.top()[2];
        pq.pop();
        if (vis[x][y]) continue;
        //cout<<x<<' '<<y<<endl;
        vis[x][y]=1;
        int h;
        if (y==11) h=0;
        elif (y==12) h=b[x];
        else h=c[v[x][y]];
        for (int i=0;i<v[x].size();i++){
            if (dis[x][i]>dis[x][y]+abs(c[v[x][i]]-h)){
                dis[x][i]=dis[x][y]+abs(c[v[x][i]]-h);
                pq.push({-dis[x][i],x,i});
            }
        }
        if (dis[x][11]>dis[x][y]+h){
            dis[x][11]=dis[x][y]+h;
            pq.push({-dis[x][11],x,11});
        }
        if (dis[x][12]>dis[x][y]+b[x]-h){
            dis[x][12]=dis[x][y]+b[x]-h;
            pq.push({-dis[x][12],x,12});
        }
        if (y>10) continue;
        auto it=s[v[x][y]].upper_bound(x);
        if (it!=s[v[x][y]].end()){
            int tox=*it,toy;
            for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
            if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
                dis[tox][toy]=dis[x][y]+abs(a[tox]-a[x]);
                pq.push({-dis[tox][toy],tox,toy});
            }
        }
        it=s[v[x][y]].lower_bound(x);
        if (it!=s[v[x][y]].begin()){
            int tox=*--it,toy;
            for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
            if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
                dis[tox][toy]=dis[x][y]+abs(a[tox]-a[x]);
                pq.push({-dis[tox][toy],tox,toy});
            }
        }
    }
    return;
}
long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t S, int32_t g) {
    n=x.size(),m=l.size();
    for (int i=0;i<n;i++) a[i+1]=x[i],b[i+1]=h[i];
    for (int j=0;j<m;j++) L[j+1]=l[j]+1,R[j+1]=r[j]+1,c[j+1]=y[j];
    for (int j=1;j<=m;j++){
        ad[L[j]].pb({c[j],j});
        er[R[j]].pb({c[j],j});
    }
    set<pair<int,int>> ms;
    for (int i=1;i<=n;i++){
        for (auto u:ad[i]) ms.ep(u);
        for (auto u:ms){
            if (u.F<=b[i]) v[i].pb(u.S),s[u.S].ep(i);
            else break;
        }
        for (auto u:er[i]) ms.erase(u);
    }
    dijkstra(S+1);
    if (dis[g+1][11]==LLONG_MAX) return -1;
    return dis[g+1][11];
}

컴파일 시 표준 에러 (stderr) 메시지

walk.cpp: In function 'void dijkstra(long long int)':
walk.cpp:31:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int i=0;i<v[x].size();i++){
      |                      ~^~~~~~~~~~~~
walk.cpp:49:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
      |                          ~^~~~~~~~~~~~~~
walk.cpp:58:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
      |                          ~^~~~~~~~~~~~~~
walk.cpp:59:29: warning: 'toy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |             if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
      |                 ~~~~~~~~~~~~^
walk.cpp:50:29: warning: 'toy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |             if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
      |                 ~~~~~~~~~~~~^

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