Submission #46709

#	Time	Username	Problem	Language	Result	Execution time	Memory
46709		eropsergeev	Soccer (JOI17_soccer)	C++14	100 / 100	1122 ms	120784 KiB

soccer

#ifdef LOCKAL
    #define _GLIBCXX_DEBUG
#endif
//#ifndef LOCKAL
    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,mmx,avx")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("unroll-all-loops")
//#endif
#include <bits/stdc++.h>
//#define TIMUS
//#define FILENAME "journey"
#ifndef TIMUS
    #include <ext/rope>
    #include <ext/pb_ds/assoc_container.hpp>
#endif // TIMUS
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int INF = INT_MAX / 2;
const ll LINF = (ll)2e18 + 666, M = 1e9 + 7;
const ld EPS = 1e-7;

#ifndef M_PI
    const ld M_PI = acos(-1);
#endif // M_PI

using namespace std;

#ifndef TIMUS
    using namespace __gnu_cxx;
    using namespace __gnu_pbds;

    template<class K, class T>
    using ordered_map = tree<K, T, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

    template<class T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

void run();

template<class T1, class T2>
inline bool mini(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

template<class T1, class T2>
inline bool maxi(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}

int main()
{
    #ifndef LOCKAL
        #ifdef FILENAME
            freopen(FILENAME".in", "r", stdin);
            freopen(FILENAME".out", "w", stdout);
        #endif // FILENAME
    #endif
    #ifndef TIMUS
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif // TIMUS
    srand(time(0));
    auto start = clock();
    run();
    #ifdef LOCKAL
        //cout << endl;
        cout << "\ntime = " << (ld)(clock() - start) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}

#define DEBUG
#if defined DEBUG && defined LOCKAL
    #define debugdo(x) x
#else
    #define debugdo(x)
#endif

#define debug_for(x) debug(#x": "); debugdo(for (auto &_x: x)) debug2(_x); debug("")
#define debug(x) debugdo(cout << x << endl)
#define debug2(x) debugdo(cout << x << " ")

// ---SOLUTION--- //

//#define FAST 1e9
#ifdef FAST
    char buf[(int)FAST];
    size_t p = 0;
    inline void *operator new(size_t n)
    {
        p += n;
        return buf + p - n;
    }
    inline void operator delete(void *){}
#endif

int n;
vector<vector<pair<int, ll>>> g;

int d[501][501];
int w, h;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

void bfs()
{
    queue<pii> q;
    for (int i = 0; i <= w; i++)
        for (int j = 0; j <= h; j++)
            if (!d[i][j])
                q.push({i, j});
    while (!q.empty())
    {
        int x = q.front().F;
        int y = q.front().S;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            if (x + dx[i] >= 0 && x + dx[i] <= w && y + dy[i] >= 0 && y + dy[i] <= h && d[x + dx[i]][y + dy[i]] == INF)
            {
                d[x + dx[i]][y + dy[i]] = d[x][y] + 1;
                q.push({x + dx[i], y + dy[i]});
            }
        }
    }
    for (int i = 0; i <= w; i++)
    {
        for (int j = 0; j <= h; j++)
        {
            debug2(d[i][j]);
        }
        debug("");
    }
}

#define pos(i, j) (((i) * (h + 1) + (j)) * 4)

ll dijk(int s, int t)
{
    vector<ll> d(n, LINF);
    d[s] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    auto relax = [&](int v)
    {
        for (auto x: g[v])
        {
            if (d[x.F] > d[v] + x.S)
            {
                d[x.F] = d[v] + x.S;
                q.push({d[x.F], x.F});
            }
        }
    };
    q.push({0, s});
    vector<bool> use(n);
    for (int i = 0; i < n; i++)
    {
        int v;
        ll dst;
        do
        {
            assert(q.size());
            v = q.top().S;
            dst = q.top().F;
            q.pop();
        }
        while (dst != d[v] || use[v]);
        use[v] = 1;
        relax(v);
    }
    debug(d[pos(1, 1)]);
    return d[t];
}

void run()
{
    int n;
    cin >> w >> h;
    for (int i = 0; i <= w; i++)
    {
        for (int j = 0; j <= h; j++)
        {
            d[i][j] = INF;
        }
    }
    ll a, b, c;
    ::n = (w + 1) * (h + 1) * 4;
    g.resize((w + 1) * (h + 1) * 4);
    cin >> a >> b >> c;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        if (i != n - 1)
            d[x[i]][y[i]] = 0;
    }
    bfs();
    for (int i = 0; i <= w; i++)
    {
        for (int j = 0; j <= h; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                if (i + dx[k] >= 0 && i + dx[k] <= w && j + dy[k] >= 0 && j + dy[k] <= h)
                {
                    //0 - simple
                    //1 - player
                    //2 - fly on x
                    //3 - fly on y
                    g[pos(i, j) + 1].pb({pos(i + dx[k], j + dy[k]) + 1, c});
                    if (k & 1)
                        g[pos(i, j) + 3].pb({pos(i + dx[k], j + dy[k]) + 3, a});
                    else
                        g[pos(i, j) + 2].pb({pos(i + dx[k], j + dy[k]) + 2, a});
                }
            }
            g[pos(i, j) + 1].pb({pos(i, j) + 2, b});
            g[pos(i, j) + 1].pb({pos(i, j) + 3, b});
            g[pos(i, j) + 2].pb({pos(i, j) + 0, 0});
            g[pos(i, j) + 3].pb({pos(i, j) + 0, 0});
            g[pos(i, j) + 0].pb({pos(i, j) + 1, d[i][j] * c});
            g[pos(i, j) + 1].pb({pos(i, j) + 0, 0});
        }
    }
    cout << dijk(pos(x[0], y[0]), pos(x[n - 1], y[n - 1]));
}
/*

*/

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:86:10: warning: unused variable 'start' [-Wunused-variable]
     auto start = clock();
          ^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65