oj.uz

Submission #1013293

# Submission time Handle Problem Language Result Execution time Memory
1013293 2024-07-03T11:40:03 Z boris_mihov Sky Walking (IOI19_walk) C++17
24 / 100
 1243 ms 447676 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 dp[MAXN];
llong solveSpecial()
{
    for (int i = 1 ; i <= m ; ++i)
    {
        if (left[i] == 1)
        {
            dp[i] = y[i];
        } else
        {
            dp[i] = INF;
            for (int j = 1 ; j < i ; ++j)
            {
                if (right[j] >= left[i])
                {
                    if (y[j] < y[i])
                    {
                        dp[i] = std::min(dp[i], dp[j] + x[left[i]] - x[left[j]] + y[i] - y[j]);
                    }

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

    llong ans = INF;
    for (int i = 1 ; i <= m ; ++i)
    {
        if (right[i] == n)
        {
            ans = std::min(ans, dp[i] + x[n] - x[left[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 11 ms 43608 KB Output is correct
2 Correct 11 ms 43356 KB Output is correct
3 Correct 11 ms 43156 KB Output is correct
4 Correct 11 ms 43356 KB Output is correct
5 Correct 12 ms 43376 KB Output is correct
6 Correct 12 ms 43404 KB Output is correct
7 Correct 11 ms 43356 KB Output is correct
8 Correct 12 ms 43356 KB Output is correct
9 Correct 11 ms 43352 KB Output is correct
10 Correct 12 ms 43356 KB Output is correct
11 Correct 12 ms 43356 KB Output is correct
12 Correct 10 ms 43356 KB Output is correct
13 Correct 11 ms 43352 KB Output is correct
14 Correct 11 ms 43352 KB Output is correct
15 Correct 12 ms 43356 KB Output is correct
16 Correct 11 ms 43356 KB Output is correct
17 Correct 12 ms 43264 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43356 KB Output is correct
2 Correct 11 ms 43356 KB Output is correct
3 Correct 509 ms 137296 KB Output is correct
4 Correct 417 ms 151128 KB Output is correct
5 Correct 214 ms 136580 KB Output is correct
6 Correct 202 ms 126028 KB Output is correct
7 Correct 218 ms 136532 KB Output is correct
8 Correct 653 ms 164164 KB Output is correct
9 Correct 236 ms 134224 KB Output is correct
10 Correct 558 ms 191260 KB Output is correct
11 Correct 211 ms 95316 KB Output is correct
12 Correct 105 ms 82256 KB Output is correct
13 Correct 413 ms 173396 KB Output is correct
14 Correct 92 ms 84128 KB Output is correct
15 Correct 112 ms 85072 KB Output is correct
16 Correct 120 ms 87632 KB Output is correct
17 Correct 102 ms 83664 KB Output is correct
18 Correct 262 ms 87240 KB Output is correct
19 Correct 21 ms 45272 KB Output is correct
20 Correct 57 ms 63824 KB Output is correct
21 Correct 96 ms 82412 KB Output is correct
22 Correct 103 ms 85088 KB Output is correct
23 Correct 156 ms 93376 KB Output is correct
24 Correct 120 ms 85136 KB Output is correct
25 Correct 114 ms 84800 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 54744 KB Output is correct
2 Runtime error 1243 ms 447676 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 54744 KB Output is correct
2 Runtime error 1243 ms 447676 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43608 KB Output is correct
2 Correct 11 ms 43356 KB Output is correct
3 Correct 11 ms 43156 KB Output is correct
4 Correct 11 ms 43356 KB Output is correct
5 Correct 12 ms 43376 KB Output is correct
6 Correct 12 ms 43404 KB Output is correct
7 Correct 11 ms 43356 KB Output is correct
8 Correct 12 ms 43356 KB Output is correct
9 Correct 11 ms 43352 KB Output is correct
10 Correct 12 ms 43356 KB Output is correct
11 Correct 12 ms 43356 KB Output is correct
12 Correct 10 ms 43356 KB Output is correct
13 Correct 11 ms 43352 KB Output is correct
14 Correct 11 ms 43352 KB Output is correct
15 Correct 12 ms 43356 KB Output is correct
16 Correct 11 ms 43356 KB Output is correct
17 Correct 12 ms 43264 KB Output is correct
18 Correct 11 ms 43356 KB Output is correct
19 Correct 11 ms 43356 KB Output is correct
20 Correct 509 ms 137296 KB Output is correct
21 Correct 417 ms 151128 KB Output is correct
22 Correct 214 ms 136580 KB Output is correct
23 Correct 202 ms 126028 KB Output is correct
24 Correct 218 ms 136532 KB Output is correct
25 Correct 653 ms 164164 KB Output is correct
26 Correct 236 ms 134224 KB Output is correct
27 Correct 558 ms 191260 KB Output is correct
28 Correct 211 ms 95316 KB Output is correct
29 Correct 105 ms 82256 KB Output is correct
30 Correct 413 ms 173396 KB Output is correct
31 Correct 92 ms 84128 KB Output is correct
32 Correct 112 ms 85072 KB Output is correct
33 Correct 120 ms 87632 KB Output is correct
34 Correct 102 ms 83664 KB Output is correct
35 Correct 262 ms 87240 KB Output is correct
36 Correct 21 ms 45272 KB Output is correct
37 Correct 57 ms 63824 KB Output is correct
38 Correct 96 ms 82412 KB Output is correct
39 Correct 103 ms 85088 KB Output is correct
40 Correct 156 ms 93376 KB Output is correct
41 Correct 120 ms 85136 KB Output is correct
42 Correct 114 ms 84800 KB Output is correct
43 Correct 44 ms 54744 KB Output is correct
44 Runtime error 1243 ms 447676 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -