oj.uz

Submission #1013324

# Submission time Handle Problem Language Result Execution time Memory
1013324 2024-07-03T12:11:04 Z boris_mihov Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 194896 KB 
#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;
const int MAXLOG = 17;

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

struct Sparse
{
    int sparse[MAXLOG][MAXN];
    int getLOG[MAXN];

    void build(int a[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            sparse[0][i] = a[i];
        }

        for (int lg = 1 ; (1 << lg) <= n ; ++lg)
        {
            for (int i = 1 ; i + (1 << lg) - 1 <= n ; ++i)
            {
                sparse[lg][i] = std::max(sparse[lg - 1][i], sparse[lg - 1][i + (1 << lg - 1)]);
            }
        }

        for (int i = 1 ; i <= n ; ++i)
        {
            getLOG[i] = getLOG[i - 1];
            if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
        }
    }

    int findMAX(int l, int r)
    {
        int lg = getLOG[r - l + 1];
        return std::max(sparse[lg][l], sparse[lg][r - (1 << lg) + 1]);
    }
};

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

    sparse.build(h);
    for (int i = 1 ; i <= m ; ++i)
    {
        int prev = left[i];
        if (map[left[i]][y[i]] == 0)
        {
            map[left[i]][y[i]] = ++cnt;
        }

        while (prev < right[i])
        {
            int l = prev, r = right[i] + 1, mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                if (sparse.findMAX(prev + 1, mid) < y[i]) l = mid;
                else r = mid;
            }

            if (map[r][y[i]] == 0)
            {
                map[r][y[i]] = ++cnt;
            }

            // std::cout << "here: " << prev << ' ' << r << ' ' << y[i] << '\n';
            g[map[prev][y[i]]].push_back({map[r][y[i]], x[r] - x[prev]});
            g[map[r][y[i]]].push_back({map[prev][y[i]], x[r] - x[prev]});
            prev = r;
        }
    }

    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(dist + 1, dist + 1 + cnt, INF);
    pq.push({0, map[s][0]});
    dist[map[s][0]] = 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 (dist[u] > dist[node] + ed)
            {
                dist[u] = dist[node] + ed;
                pq.push({-dist[u], u});
            }
        }
    }

	return (dist[map[t][0]] == INF ? -1 : dist[map[t][0]]);
}

llong dpL[MAXN];
llong dpR[MAXN];
llong solveSpecial()
{
    for (int i = 1 ; i <= m ; ++i)
    {
        if (left[i] == 1)
        {
            dpL[i] = y[i];
            dpR[i] = y[i] + x[right[i]];
        } else
        {
            dpL[i] = INF;
            dpR[i] = INF;
            for (int j = 1 ; j < i ; ++j)
            {
                if (right[j] >= left[i])
                {
                    if (y[j] < y[i])
                    {
                        dpL[i] = std::min(dpL[i], dpL[j] + x[left[i]] - x[left[j]] + y[i] - y[j]);
                    }

                    if (y[j] >= y[i] && y[j] <= h[left[i]])
                    {
                        dpL[i] = std::min(dpL[i], dpL[j] + x[left[i]] - x[left[j]] + y[j] - y[i]);
                    }
                }

                if (right[j] >= left[i] && right[j] <= right[i])
                {
                    if (y[j] >= y[i])
                    {
                        dpR[i] = std::min(dpR[i], dpR[j] + y[j] - y[i] + x[right[i]] - x[right[j]]);
                    }

                    if (y[j] <= y[i] && y[i] <= h[right[i]])
                    {
                        dpR[i] = std::min(dpR[i], dpR[j] + y[i] - y[j] + x[right[i]] - x[right[j]]);
                    }
                }
            }

            dpR[i] = std::min(dpR[i], dpL[i] + x[right[i]] - x[left[i]]);
        }
    }

    llong ans = INF;
    for (int i = 1 ; i <= m ; ++i)
    {
        if (right[i] == n)
        {
            ans = std::min(ans, dpR[i] + y[i]);
        }
    }

    return ans;
}

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 + 1; ::t = t + 1;

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

    std::vector <int> perm(m);
    std::iota(perm.begin(), perm.end(), 0);
    std::sort(perm.begin(), perm.end(), [&](int x, int y)
    {
        return l[x] < l[y];
    });

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

    if (::s == 1 && ::t == n) return solveSpecial();
    return solve();
}

Compilation message

walk.cpp: In member function 'void Sparse::build(int*)':
walk.cpp:51:89: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   51 |                 sparse[lg][i] = std::max(sparse[lg - 1][i], sparse[lg - 1][i + (1 << lg - 1)]);
      |                                                                                      ~~~^~~
walk.cpp:58:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   58 |             if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
      |                       ~~~~~~~~~~^~~
walk.cpp: In function 'llong solve()':
walk.cpp:91:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |                 mid = l + r >> 1;
      |                       ~~^~~
walk.cpp: At global scope:
walk.cpp:32:9: warning: '{anonymous}::cntNodes' defined but not used [-Wunused-variable]
   32 |     int cntNodes;
      |         ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 41820 KB Output is correct
2 Correct 16 ms 41820 KB Output is correct
3 Correct 16 ms 41692 KB Output is correct
4 Correct 16 ms 41820 KB Output is correct
5 Correct 16 ms 41820 KB Output is correct
6 Correct 17 ms 41816 KB Output is correct
7 Correct 17 ms 41872 KB Output is correct
8 Correct 16 ms 41820 KB Output is correct
9 Correct 16 ms 41724 KB Output is correct
10 Correct 17 ms 41820 KB Output is correct
11 Correct 16 ms 41816 KB Output is correct
12 Correct 16 ms 41820 KB Output is correct
13 Correct 20 ms 41820 KB Output is correct
14 Correct 16 ms 41764 KB Output is correct
15 Correct 16 ms 41820 KB Output is correct
16 Correct 16 ms 41816 KB Output is correct
17 Correct 20 ms 41820 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 41820 KB Output is correct
2 Correct 16 ms 41820 KB Output is correct
3 Correct 523 ms 138080 KB Output is correct
4 Correct 366 ms 154716 KB Output is correct
5 Correct 204 ms 140112 KB Output is correct
6 Correct 198 ms 129620 KB Output is correct
7 Correct 227 ms 140404 KB Output is correct
8 Correct 700 ms 164856 KB Output is correct
9 Correct 258 ms 137808 KB Output is correct
10 Correct 577 ms 194896 KB Output is correct
11 Correct 221 ms 97104 KB Output is correct
12 Correct 1733 ms 53516 KB Output is correct
13 Correct 1834 ms 53660 KB Output is correct
14 Correct 97 ms 84044 KB Output is correct
15 Correct 101 ms 85328 KB Output is correct
16 Correct 125 ms 85588 KB Output is correct
17 Correct 110 ms 83536 KB Output is correct
18 Correct 43 ms 52052 KB Output is correct
19 Correct 19 ms 43864 KB Output is correct
20 Correct 58 ms 62784 KB Output is correct
21 Correct 1775 ms 51848 KB Output is correct
22 Correct 1737 ms 52728 KB Output is correct
23 Execution timed out 4045 ms 52180 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 45316 KB Output is correct
2 Execution timed out 4056 ms 48600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 45316 KB Output is correct
2 Execution timed out 4056 ms 48600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 41820 KB Output is correct
2 Correct 16 ms 41820 KB Output is correct
3 Correct 16 ms 41692 KB Output is correct
4 Correct 16 ms 41820 KB Output is correct
5 Correct 16 ms 41820 KB Output is correct
6 Correct 17 ms 41816 KB Output is correct
7 Correct 17 ms 41872 KB Output is correct
8 Correct 16 ms 41820 KB Output is correct
9 Correct 16 ms 41724 KB Output is correct
10 Correct 17 ms 41820 KB Output is correct
11 Correct 16 ms 41816 KB Output is correct
12 Correct 16 ms 41820 KB Output is correct
13 Correct 20 ms 41820 KB Output is correct
14 Correct 16 ms 41764 KB Output is correct
15 Correct 16 ms 41820 KB Output is correct
16 Correct 16 ms 41816 KB Output is correct
17 Correct 20 ms 41820 KB Output is correct
18 Correct 16 ms 41820 KB Output is correct
19 Correct 16 ms 41820 KB Output is correct
20 Correct 523 ms 138080 KB Output is correct
21 Correct 366 ms 154716 KB Output is correct
22 Correct 204 ms 140112 KB Output is correct
23 Correct 198 ms 129620 KB Output is correct
24 Correct 227 ms 140404 KB Output is correct
25 Correct 700 ms 164856 KB Output is correct
26 Correct 258 ms 137808 KB Output is correct
27 Correct 577 ms 194896 KB Output is correct
28 Correct 221 ms 97104 KB Output is correct
29 Correct 1733 ms 53516 KB Output is correct
30 Correct 1834 ms 53660 KB Output is correct
31 Correct 97 ms 84044 KB Output is correct
32 Correct 101 ms 85328 KB Output is correct
33 Correct 125 ms 85588 KB Output is correct
34 Correct 110 ms 83536 KB Output is correct
35 Correct 43 ms 52052 KB Output is correct
36 Correct 19 ms 43864 KB Output is correct
37 Correct 58 ms 62784 KB Output is correct
38 Correct 1775 ms 51848 KB Output is correct
39 Correct 1737 ms 52728 KB Output is correct
40 Execution timed out 4045 ms 52180 KB Time limit exceeded
41 Halted 0 ms 0 KB -