제출 #1071368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071368		becaido	Sky Walking (IOI19_walk)	C++17	24 / 100	3273 ms	1048576 KiB

walk

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "walk.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const ll INF = 1e18;
const int SIZE = 1e5 + 5;

int n, m, s, e, sz;
vector<int> y[SIZE];
int x[SIZE], h[SIZE];
vector<pair<int, int>> P;
tuple<int, int, int> a[SIZE];
vector<tuple<int, int, int>> ed;

int get_id(int i, int y) {
    return lower_bound(P.begin(), P.end(), make_pair(i, y)) - P.begin() + 1;
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g) {
    n = _x.size(), m = _l.size();
    s = _s + 1, e = _g + 1;
    FOR (i, 1, n) {
        x[i] = _x[i - 1];
        h[i] = _h[i - 1];
    }
    FOR (i, 1, m) {
        _l[i - 1]++, _r[i - 1]++;
        a[i] = {_y[i - 1], _l[i - 1], _r[i - 1]};
    }

    set<int> st;
    FOR (i, 1, n) st.insert(i), y[i].pb(0);
    vector<tuple<int, int, int>> all;
    FOR (i, 1, m) all.pb(a[i]);
    FOR (i, 1, n) all.pb(h[i], x[i], -i);
    sort(all.begin(), all.end(), [&](auto x, auto y) {
        return get<0>(x) != get<0>(y) ? get<0>(x) < get<0>(y) : get<2>(x) > get<2>(y);
    });
    for (auto [a, b, c] : all) {
        if (c < 0) {
            st.erase(-c);
            continue;
        }
        int last = 0;
        for (auto it = st.lower_bound(b); it != st.end() && *it <= c; it++) {
            y[*it].pb(a);
            if (last != 0) ed.pb(last, *it, a);
            last = *it;
        }
    }
    FOR (i, 1, n) {
        sort(y[i].begin(), y[i].end());
        y[i].erase(unique(y[i].begin(), y[i].end()), y[i].end());
        for (int iy : y[i]) P.pb(i, iy);
        sz += y[i].size();
    }
    sort(ed.begin(), ed.end());
    ed.erase(unique(ed.begin(), ed.end()), ed.end());

    vector<ll> dis(sz + 1, INF);
    vector<vector<pair<int, int>>> adj(sz + 1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (auto [i, j, y] : ed) {
        int u = get_id(i, y), v = get_id(j, y);
        // debug(i, j, y);
        adj[u].pb(v, x[j] - x[i]);
        adj[v].pb(u, x[j] - x[i]);
    }
    FOR (i, 1, n) for (int j = 0; j + 1 < y[i].size(); j++) {
        // debug(i, y[i][j], y[i][j + 1]);
        int u = get_id(i, y[i][j]), v = get_id(i, y[i][j + 1]);
        adj[u].pb(v, y[i][j + 1] - y[i][j]);
        adj[v].pb(u, y[i][j + 1] - y[i][j]);
    }
    s = get_id(s, 0), e = get_id(e, 0);
    pq.emplace(dis[s] = 0, s);
    while (pq.size()) {
        auto [d, pos] = pq.top();
        pq.pop();
        if (d > dis[pos]) continue;
        for (auto [np, w] : adj[pos]) if (d + w < dis[np]) {
            pq.emplace(dis[np] = d + w, np);
        }
    }
    return dis[e] == INF ? -1 : dis[e];
}

/*
in1
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
out1
27

in2
5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
out2
21
*/

컴파일 시 표준 에러 (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:92:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     FOR (i, 1, n) for (int j = 0; j + 1 < y[i].size(); j++) {
      |                                   ~~~~~~^~~~~~~~~~~~~

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