oj.uz

Submission #907562

# Submission time Handle Problem Language Result Execution time Memory
907562 2024-01-15T21:07:41 Z andrei_iorgulescu Soccer (JOI17_soccer) C++14
100 / 100
 1106 ms 48496 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;
int dl[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};

struct stare
{
    int i,j,q;
};

int h,w,a,b,c,n;
pair<int,int>p[100005];
int d[505][505][5];
bool om[505][505];
int dmin[505][505];

class Compare
{
public:
    bool operator()(pair<int,stare>cine1, pair<int,stare>cine2)
    {
        return cine1.first < cine2.first;
    }
};

void calc_dmin()
{
    for (int i = 0; i <= h; i++)
        for (int j = 0; j <= w; j++)
            dmin[i][j] = inf;
    queue<pair<int,int>> qq;
    for (int i = 1; i <= n; i++)
    {
        qq.push(p[i]);
        dmin[p[i].first][p[i].second] = 0;
    }
    while (!qq.empty())
    {
        pair<int,int> nod = qq.front();
        qq.pop();
        for (int i = 0; i < 4; i++)
        {
            int l = nod.first + dl[i],c = nod.second + dc[i];
            if (l >= 0 and l <= h and c >= 0 and c <= w and dmin[l][c] == inf)
            {
                dmin[l][c] = 1 + dmin[nod.first][nod.second];
                qq.push({l,c});
            }
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> h >> w >> a >> b >> c >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].first >> p[i].second,om[p[i].first][p[i].second] = true;
    calc_dmin();
    for (int i = 0; i <= h; i++)
    {
        for (int j = 0; j <= w; j++)
        {
            for (int q = 0; q < 5; q++)
                d[i][j][q] = inf;
        }
    }
    priority_queue<pair<int,stare>, vector<pair<int,stare>>, Compare>pq;
    stare initial;
    initial.i = p[1].first;
    initial.j = p[1].second;
    initial.q = 0;
    pq.push({0,initial});
    while (!pq.empty())
    {
        int timp = -pq.top().first;
        stare nod = pq.top().second;
        //cout << timp << ' ' << nod.i << ' ' << nod.j << ' ' << nod.q << endl;
        pq.pop();
        if (d[nod.i][nod.j][nod.q] == inf)
        {
            d[nod.i][nod.j][nod.q] = timp;
            if (nod.q == 0)
            {
                stare vecin;
                vecin.i = nod.i;
                vecin.j = nod.j;
                for (vecin.q = 1; vecin.q <= 4; vecin.q++)
                    pq.push({-(timp + b),vecin});
                vecin.q = 0;
                for (int cv = 0; cv < 4; cv++)
                {
                    vecin.i = nod.i + dl[cv];
                    vecin.j = nod.j + dc[cv];
                    if (vecin.i >= 0 and vecin.i <= h and vecin.j >= 0 and vecin.j <= w)
                        pq.push({-(timp + c),vecin});
                }
            }
            else
            {
                stare vecin;
                vecin.i = nod.i;
                vecin.j = nod.j;
                vecin.q = 0;
                pq.push({-(timp + c * dmin[nod.i][nod.j]),vecin});
                vecin.q = nod.q;
                vecin.i = nod.i + dl[nod.q - 1];
                vecin.j = nod.j + dc[nod.q - 1];
                if (vecin.i >= 0 and vecin.i <= h and vecin.j >= 0 and vecin.j <= w)
                    pq.push({-(timp + a),vecin});
            }
        }
    }
    cout << d[p[n].first][p[n].second][0];
    /*for (int i = 0; i <= 6; i++)
    {
        for (int j = 0; j <= 5; j++)
        {
            for (int q = 0; q <= 4; q++)
                cout << i << ' ' << j << ' ' << q << ' ' << d[i][j][q] << endl;
        }
    }*/
    return 0;
}

/**
d[i][j][0/1/2/3/4] = costul minim ca mingea sa fie la pozitia i si fie sa stea la un om (0) fie sa aiba momentum in dir 1/2/3/4
calculez d cu un dijkstra
din starea (i,j,0) ma pot duce in starea (i,j,1/2/3/4) cu cost B
din starea (i,j,dir) ma pot duce in starea (i_vec,j_vec,dir) cu cost A unde (i_vec,j_vec) e vecina pe directia dir cu (i,j)
din starea (i,j,dir) ma pot duce in starea (i,j,0) cu cost 0 doar daca am om in pozitia (i,j)
din starea (i,j,0) ma pot duce in starea (i_vec,j_vec,0) cu cost C unde (i_vec,j_vec) este vecin pe orice directie cu (i,j)
raspunsul meu este d[sN][tN][0]
initial pornesc cu d[s1][t1][0] = 0
**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 16328 KB Output is correct
2 Correct 2 ms 6896 KB Output is correct
3 Correct 573 ms 29628 KB Output is correct
4 Correct 686 ms 45940 KB Output is correct
5 Correct 162 ms 22204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 47180 KB Output is correct
2 Correct 793 ms 46368 KB Output is correct
3 Correct 507 ms 30424 KB Output is correct
4 Correct 619 ms 31296 KB Output is correct
5 Correct 544 ms 31056 KB Output is correct
6 Correct 674 ms 31060 KB Output is correct
7 Correct 830 ms 46660 KB Output is correct
8 Correct 655 ms 47016 KB Output is correct
9 Correct 784 ms 47524 KB Output is correct
10 Correct 70 ms 22204 KB Output is correct
11 Correct 791 ms 47780 KB Output is correct
12 Correct 847 ms 46788 KB Output is correct
13 Correct 475 ms 30608 KB Output is correct
14 Correct 821 ms 46448 KB Output is correct
15 Correct 639 ms 46756 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 16328 KB Output is correct
2 Correct 2 ms 6896 KB Output is correct
3 Correct 573 ms 29628 KB Output is correct
4 Correct 686 ms 45940 KB Output is correct
5 Correct 162 ms 22204 KB Output is correct
6 Correct 832 ms 47180 KB Output is correct
7 Correct 793 ms 46368 KB Output is correct
8 Correct 507 ms 30424 KB Output is correct
9 Correct 619 ms 31296 KB Output is correct
10 Correct 544 ms 31056 KB Output is correct
11 Correct 674 ms 31060 KB Output is correct
12 Correct 830 ms 46660 KB Output is correct
13 Correct 655 ms 47016 KB Output is correct
14 Correct 784 ms 47524 KB Output is correct
15 Correct 70 ms 22204 KB Output is correct
16 Correct 791 ms 47780 KB Output is correct
17 Correct 847 ms 46788 KB Output is correct
18 Correct 475 ms 30608 KB Output is correct
19 Correct 821 ms 46448 KB Output is correct
20 Correct 639 ms 46756 KB Output is correct
21 Correct 166 ms 16780 KB Output is correct
22 Correct 846 ms 30820 KB Output is correct
23 Correct 841 ms 30296 KB Output is correct
24 Correct 996 ms 30004 KB Output is correct
25 Correct 774 ms 30648 KB Output is correct
26 Correct 721 ms 31144 KB Output is correct
27 Correct 326 ms 15592 KB Output is correct
28 Correct 416 ms 16404 KB Output is correct
29 Correct 648 ms 24988 KB Output is correct
30 Correct 525 ms 21152 KB Output is correct
31 Correct 1030 ms 48008 KB Output is correct
32 Correct 1106 ms 48496 KB Output is correct
33 Correct 644 ms 31268 KB Output is correct
34 Correct 1022 ms 47528 KB Output is correct
35 Correct 372 ms 17492 KB Output is correct