Submission #1013254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013254		boris_mihov	Sky Walking (IOI19_walk)	C++17	0 / 100	1031 ms	444236 KiB

walk

#include "walk.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>
#include <map>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INTERSECTIONS = 10 + 5;
const llong INF = 1e18;
const int INTINF = 1e9;

namespace
{
    int cnt;
    int n, m;
    int s, t;
    int h[MAXN];
    int x[MAXN];
    int l[MAXN];
    int r[MAXN];
    int y[MAXN];
    std::map <int,int> map[MAXN];
    bool vis[MAXN * INTERSECTIONS];
    llong dists[MAXN * INTERSECTIONS];
    std::vector <std::pair <int,int>> g[MAXN * INTERSECTIONS]; 
    int cntNodes;
}

llong solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        map[i][0] = ++cnt;
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        int prev = -1;
        // std::cout << "building: " << i << ' ' << l[i] << ' ' << r[i] << ' ' << y[i] << '\n';
        for (int j = l[i] ; j <= r[i] ; ++j)
        {
            if (y[i] <= h[j])
            {
                if (map[j][y[i]] == 0)
                {
                    map[j][y[i]] = ++cnt;
                }

                if (prev != -1)
                {
                    // std::cout << "edge hor: " << x[prev] << ' ' << y[i] << ' ' << x[j] << ' ' << y[i] << ' ' << map[prev][y[i]] << ' ' << << '\n';
                    g[map[prev][y[i]]].push_back({map[j][y[i]], x[j] - x[prev]});
                    g[map[j][y[i]]].push_back({map[prev][y[i]], x[j] - x[prev]});
                }

                prev = j;
            }
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        auto prev = map[i].begin();
        for (auto curr = std::next(map[i].begin()) ; curr != map[i].end() ; ++curr)
        {
            // std::cout << "edge ver: " << x[i] << ' ' << prev->first << ' ' << x[i] << ' ' << curr->first << '\n';
            g[prev->second].push_back({curr->second, curr->first - prev->first});
            g[curr->second].push_back({prev->second, curr->first - prev->first});
            prev = curr;
        }
    }

    std::priority_queue <std::pair <llong,int>> pq;
    std::fill(dists + 1, dists + 1 + cnt, INF);
    pq.push({0, 1});
    dists[1] = 0;

    while (pq.size())
    {
        auto [d, node] = pq.top();
        pq.pop();

        if (vis[node])
        {
            continue;
        }

        vis[node] = true;
        for (const auto &[u, ed] : g[node])
        {
            if (dists[u] > dists[node] + ed)
            {
                dists[u] = dists[node] + ed;
                pq.push({-dists[u], u});
            }
        }
    }

	return (dists[n] == INF ? -1 : dists[n]);
}

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 t) 
{
    n = x.size();
    m = l.size();
    ::s = s; ::t = t;

    for (int i = 0 ; i < n ; ++i)
    {
        ::h[i + 1] = h[i];
        ::x[i + 1] = x[i];
    }

    for (int i = 0 ; i < m ; ++i)
    {
        ::l[i + 1] = l[i] + 1;
        ::r[i + 1] = r[i] + 1;
        ::y[i + 1] = y[i];
    }

    return solve();
}

Compilation message (stderr)

walk.cpp:31:9: warning: '{anonymous}::cntNodes' defined but not used [-Wunused-variable]
   31 |     int cntNodes;
      |         ^~~~~~~~

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