oj.uz

Submission #46709

# Submission time Handle Problem Language Result Execution time Memory
46709 2018-04-22T15:32:40 Z eropsergeev Soccer (JOI17_soccer) C++14
100 / 100
 1122 ms 120784 KB 
#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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 29588 KB Output is correct
2 Correct 2 ms 29588 KB Output is correct
3 Correct 850 ms 119716 KB Output is correct
4 Correct 853 ms 119928 KB Output is correct
5 Correct 197 ms 119928 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 854 ms 119928 KB Output is correct
2 Correct 930 ms 119928 KB Output is correct
3 Correct 613 ms 119928 KB Output is correct
4 Correct 705 ms 119928 KB Output is correct
5 Correct 650 ms 119928 KB Output is correct
6 Correct 787 ms 119928 KB Output is correct
7 Correct 887 ms 119928 KB Output is correct
8 Correct 833 ms 119928 KB Output is correct
9 Correct 855 ms 119964 KB Output is correct
10 Correct 144 ms 119964 KB Output is correct
11 Correct 836 ms 119964 KB Output is correct
12 Correct 863 ms 119964 KB Output is correct
13 Correct 620 ms 119964 KB Output is correct
14 Correct 892 ms 119992 KB Output is correct
15 Correct 734 ms 119992 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 29588 KB Output is correct
2 Correct 2 ms 29588 KB Output is correct
3 Correct 850 ms 119716 KB Output is correct
4 Correct 853 ms 119928 KB Output is correct
5 Correct 197 ms 119928 KB Output is correct
6 Correct 854 ms 119928 KB Output is correct
7 Correct 930 ms 119928 KB Output is correct
8 Correct 613 ms 119928 KB Output is correct
9 Correct 705 ms 119928 KB Output is correct
10 Correct 650 ms 119928 KB Output is correct
11 Correct 787 ms 119928 KB Output is correct
12 Correct 887 ms 119928 KB Output is correct
13 Correct 833 ms 119928 KB Output is correct
14 Correct 855 ms 119964 KB Output is correct
15 Correct 144 ms 119964 KB Output is correct
16 Correct 836 ms 119964 KB Output is correct
17 Correct 863 ms 119964 KB Output is correct
18 Correct 620 ms 119964 KB Output is correct
19 Correct 892 ms 119992 KB Output is correct
20 Correct 734 ms 119992 KB Output is correct
21 Correct 235 ms 119992 KB Output is correct
22 Correct 1078 ms 119992 KB Output is correct
23 Correct 952 ms 119992 KB Output is correct
24 Correct 1122 ms 119992 KB Output is correct
25 Correct 1032 ms 119992 KB Output is correct
26 Correct 1052 ms 119992 KB Output is correct
27 Correct 758 ms 119992 KB Output is correct
28 Correct 679 ms 119992 KB Output is correct
29 Correct 914 ms 119992 KB Output is correct
30 Correct 706 ms 119992 KB Output is correct
31 Correct 997 ms 119992 KB Output is correct
32 Correct 1097 ms 120784 KB Output is correct
33 Correct 945 ms 120784 KB Output is correct
34 Correct 1067 ms 120784 KB Output is correct
35 Correct 631 ms 120784 KB Output is correct