Submission #580698

#	Time	Username	Problem	Language	Result	Execution time	Memory
580698		georgievskiy	Sky Walking (IOI19_walk)	C++14	10 / 100	4091 ms	699080 KiB

walk

#pragma GCC optimize("O3")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx2")

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sint signed
#define int long long

#define pii pair<int, int>

int min_distance(std::vector<sint> x, std::vector<sint> h, std::vector<sint> l, std::vector<sint> r, std::vector<sint> y, sint ss, sint gg) {
    int n = x.size(), m = l.size();
    vector<vector<pii>> g;
    vector<vector<pii>> c(n);
    int t = 0;
    for (int j = 0; j < m; j++) {
        int last = -1, lp;
        for (int i = l[j]; i <= r[j]; i++) {
            if (h[i] < y[j])
                continue;
            c[i].push_back({y[j], t++});
            g.push_back(vector<pii>());
            if (last != -1) {
                g[lp].push_back({t - 1, x[i] - x[last]});
                g[t - 1].push_back({lp, x[i] - x[last]});
            }
            last = i, lp = t - 1;
        }
    }

    int s = 0, f = 0;
    g.push_back(vector<pii>());
    g.push_back(vector<pii>());
    for (int i = 0; i < n; i++) {
        if (i == ss) {
            s = t;
            c[i].push_back({0, t++});
        }
        if (i == gg) {
            f = t;
            c[i].push_back({0, t++});
        }
        sort(c[i].begin(), c[i].end());
        for (int j = 0; j < (int)c[i].size() - 1; j++) {
            int v = c[i][j].second, u = c[i][j + 1].second;
            int d = c[i][j + 1].first - c[i][j].first;
            g[v].push_back({u, d});
            g[u].push_back({v, d});
        }
    }

    //for (int i = 0; i < t; i++) {
    //    cout << i << " : " ;
    //    for (pii j : g[i])
    //        cout << "{ " << j.first << ' ' << j.second << " }  ";
    //    cout << '\n';
    //}

    int a = 0;

    priority_queue<pii, vector<pii>, greater<pii>> q;
    const int inf = 2e18;

    vector<int> d(t, inf);
    q.push({0, s});

    while (q.size()) {
        int v = q.top().second, dst = q.top().first;
        q.pop();
        if (d[v] != inf)
            continue;
        d[v] = dst;
        for (auto u : g[v]) {
            if (d[u.first] == inf) {
                q.push({dst + u.second, u.first});
            }
        }
    }

    if (d[f] == inf)
        return -1;
    else
        return d[f];
}

Compilation message (stderr)

walk.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("unroll-loops")
      | 
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:61:9: warning: unused variable 'a' [-Wunused-variable]
   61 |     int a = 0;
      |         ^

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