Submission #281695

#	Time	Username	Problem	Language	Result	Execution time	Memory
281695		kartel	Sky Walking (IOI19_walk)	C++14	0 / 100	49 ms	5752 KiB

walk

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "walk.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define pb push_back
#define N +1005
//#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define Max_A int(1e9)
//#define el endl
#define pii pair <int, int>
#define piii pair <int, pair <int, int> >
#define psi pair <string, int>
#define err ld(1e-9)
#define Max_S int(3e6)
#define last(x) x.back()
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

vi houses[N];
ll d[N][N];
int i, j;
bool lines[N][N];
set <pair <int, pii> > q;

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g)
{
    int n = sz(x);
    int m = sz(l);

    for (i = 0; i < m; i++)
    {
        houses[i].clear();

        for (j = l[i]; j <= r[i]; j++)
        {
            if (y[i] <= h[j])
                lines[j][i] = 1, houses[i].pb(j);
        }
    }

    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
           d[i][j] = 1e18;

    for (i = 0; i < m; i++)
        {
            if (!lines[s][i])
                continue;

            d[s][i] = y[i];
            q.insert({d[s][i], {s, i}});
        }


    while (sz(q))
    {
        int v = (*q.begin()).S.F;
        int line = (*q.begin()).S.S;
        int now_h = y[line];
        q.erase(q.begin());

        for (int i = 0; i < m; i++)
        {
            if (!lines[v][i])
                continue;

            if (d[v][i] > d[v][line] + abs(y[line] - y[i]))
                {
                    if (q.find({d[v][i], {v, i}}) != q.end())
                        q.erase({d[v][i], {v, i}});
                    d[v][i] = d[v][line] + abs(y[line] - y[i]);
                    q.insert({{d[v][i], {v, i}}});
                }
        }

        for (auto house : houses[line])
        {
            if (house == v || !lines[house][line])
                continue;

            if (d[house][line] > d[v][line] + abs(x[house] - x[v]))
            {
                if (q.find({d[house][line], {house, line}}) != q.end())
                    q.erase({d[house][line], {house, line}});
                d[house][line] = d[v][line] + abs(x[house] - x[v]);
                q.insert({{d[house][line], {house, line}}});
            }
        }
    }

    ll ans = 1e18;

    for (int i = 0; i < m; i++)
    {
        if (!lines[g][i])
            continue;

        ans = min(ans, d[g][i] + y[i]);
    }

    return ans;
}

//int main()
//{
//    srand(time(0));
//    cout.precision(3);
//    cout << fixed;
//    ios_base::sync_with_stdio(0);
//    iostream::sync_with_stdio(0);
//    ios::sync_with_stdio(0);
//    cin.tie(NULL);
//    cout.tie(NULL);
//
////    in("input.txt");
////    out("output.txt");
//
//
//}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:80:13: warning: unused variable 'now_h' [-Wunused-variable]
   80 |         int now_h = y[line];
      |             ^~~~~

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