제출 #472901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472901		dxz05	Sky Walking (IOI19_walk)	C++14	10 / 100	4073 ms	1048576 KiB

walk

#pragma GCC optimize("Ofast,O2,O3")
#pragma GCC target("avx,avx2")

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MP make_pair

const int MAXN = 2e6 + 3e2;

void sort(vector<int> &l, vector<int> &r, vector<int> &y){
    vector<pair<int, pair<int, int>>> vec(y.size());
    for (int i = 0; i < y.size(); i++){
        vec[i] = MP(y[i], MP(l[i], r[i]));
    }
    sort(vec.begin(), vec.end());

    for (int i = 0; i < y.size(); i++){
        y[i] = vec[i].first;
        l[i] = vec[i].second.first;
        r[i] = vec[i].second.second;
    }
}

map<int, int> mp[MAXN];
int next_id = 0;
vector<pair<int, int>> points[MAXN];

int id(int i, int h){
    if (mp[i].find(h) != mp[i].end()) return mp[i][h];
    return mp[i][h] = next_id++;
}

vector<pair<int, int>> g[MAXN];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int start, int finish) {
    int n = x.size(), m = y.size();
    sort(l, r, y);

    for (int i = 0; i < n; i++){
        points[i].emplace_back(id(i, 0), 0);
    }

    for (int i = 0; i < m; i++){
        //cout << l[i] << ' ' << r[i] << ' ' << y[i] << endl;
        int last = l[i];
        for (int j = l[i]; j <= r[i]; j++){
            if (y[i] > h[j]) continue;
            int a = id(j, y[i]);
            points[j].emplace_back(a, y[i]);

            if (j > l[i]) {
                int b = id(last, y[i]);
                g[a].emplace_back(b, x[j] - x[last]);
                g[b].emplace_back(a, x[j] - x[last]);
            }

            last = j;
        }
    }

    for (int i = 0; i < n; i++){
        if (points[i].back().second != h[i]) points[i].emplace_back(id(i, h[i]), h[i]);
//        cout << i << endl;
        for (int j = 1; j < points[i].size(); j++){
//            cout << points[i][j].first << ' ' << points[i][j].second << endl;
            int a = points[i][j - 1].first, b = points[i][j].first, w = points[i][j].second - points[i][j - 1].second;
            assert(w >= 0);
            g[a].emplace_back(b, w);
            g[b].emplace_back(a, w);
        }
    }

    int k = next_id;
    vector<ll> d(k, 1e18);
    vector<bool> processed(k, false);
    d[start] = 0;

    priority_queue<pair<ll, int>> pq;
    pq.push(MP(0, start));

    while (!pq.empty()){
        int v = pq.top().second; pq.pop();
        if (processed[v]) continue;
        processed[v] = true;

        for (auto e : g[v]){
            int u = e.first, w = e.second;
            if (d[u] > d[v] + w){
                d[u] = d[v] + w;
                pq.push(MP(-d[u], u));
            }
        }

    }

    if (!processed[finish]) return -1;

	return d[finish];
}

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

walk.cpp: In function 'void sort(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
walk.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < y.size(); i++){
      |                     ~~^~~~~~~~~~
walk.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < y.size(); i++){
      |                     ~~^~~~~~~~~~
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:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int j = 1; j < points[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~

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