oj.uz

Submission #1000547

# Submission time Handle Problem Language Result Execution time Memory
1000547 2024-06-17T17:16:41 Z mispertion Soccer (JOI17_soccer) C++17
35 / 100
 1571 ms 262144 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 500+10;
const int M = 7e6 + 1;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 2;

int mult(int a, int b) {
    return a * 1LL * b % mod;
}

int sum(int a, int b) { 
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}

ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

int di[] = {0, 0, -1, 1};
int dj[] = {1, -1, 0, 0};
int H, W, n;
int a, b, c, mnd[N][N], used[N][N], d[N][N];
pii ps[100005];

void dijkstra(int si, int sj){
    for(int i = 0; i <= H; i++)
        for(int j = 0; j <= W; j++)
            d[i][j] = infl;
    d[si][sj] = 0;
    priority_queue<pair<int, pii>> st;
    st.push({0, {si, sj}});
    while(!st.empty()){
        int vi = st.top().S.F, vj = st.top().S.S;
        if(-st.top().F != d[vi][vj]){
            st.pop();
            continue;
        }
        st.pop();
        for(int dir = 0; dir < 4; dir++){
            int ni = vi + di[dir], nj = vj + dj[dir];
            if(ni >= 0 && ni <= H && nj >= 0 && nj <= W && d[ni][nj] > d[vi][vj] + c){
                d[ni][nj] = d[vi][vj] + c;
                st.push({-d[ni][nj], {ni, nj}});
            }
        }
        for(int i = 0; i <= H; i++){
            if(i == vi) continue;
            if(d[i][vj] > (d[vi][vj] + mnd[i][vj] * c + a * abs(i - vi) + b)){
                d[i][vj] = (d[vi][vj] + mnd[i][vj] * c + a * abs(i - vi) + b);
                st.push({-d[i][vj], {i, vj}});
            }
        }
        for(int j = 0; j <= W; j++){
            if(j == vj) continue;
            if(d[vi][j] > (d[vi][vj] + mnd[vi][j] * c + a * abs(j - vj) + b)){
                d[vi][j] = (d[vi][vj] + mnd[vi][j] * c + a * abs(j - vj) + b);
                st.push({-d[vi][j], {vi, j}});
            }
        }
    }
}

void solve(){
    cin >> H >> W;
    cin >> a >> b >> c;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> ps[i].F >> ps[i].S;
    }
    queue<pii> q;
    for(int i = 1; i <= n; i++){
        q.push({ps[i].F, ps[i].S});
        used[ps[i].F][ps[i].S] = 1;
    }
    while(!q.empty()){
        int vi = q.front().F, vj = q.front().S;
        q.pop();
        for(int dir = 0; dir < 4; dir++){
            int ni = vi + di[dir], nj = vj + dj[dir];
            if(ni >= 0 && ni <= H && nj >= 0 && nj <= W && !used[ni][nj]){
                used[ni][nj] = 1;
                mnd[ni][nj] = mnd[vi][vj] + 1;
                q.push({ni, nj});
            }
        }
    }
    dijkstra(ps[1].F, ps[1].S);
    cout << d[ps[n].F][ps[n].S] << '\n';
}

signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 28712 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 1571 ms 105168 KB Output is correct
4 Correct 1191 ms 55684 KB Output is correct
5 Correct 175 ms 7880 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 12604 KB Output is correct
2 Correct 701 ms 12844 KB Output is correct
3 Correct 471 ms 11464 KB Output is correct
4 Correct 613 ms 12764 KB Output is correct
5 Correct 490 ms 12796 KB Output is correct
6 Correct 622 ms 12744 KB Output is correct
7 Correct 673 ms 13052 KB Output is correct
8 Correct 641 ms 12808 KB Output is correct
9 Correct 703 ms 13068 KB Output is correct
10 Correct 80 ms 8168 KB Output is correct
11 Correct 652 ms 13064 KB Output is correct
12 Correct 744 ms 12760 KB Output is correct
13 Correct 426 ms 11464 KB Output is correct
14 Correct 719 ms 13048 KB Output is correct
15 Correct 514 ms 12808 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 28712 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 1571 ms 105168 KB Output is correct
4 Correct 1191 ms 55684 KB Output is correct
5 Correct 175 ms 7880 KB Output is correct
6 Correct 646 ms 12604 KB Output is correct
7 Correct 701 ms 12844 KB Output is correct
8 Correct 471 ms 11464 KB Output is correct
9 Correct 613 ms 12764 KB Output is correct
10 Correct 490 ms 12796 KB Output is correct
11 Correct 622 ms 12744 KB Output is correct
12 Correct 673 ms 13052 KB Output is correct
13 Correct 641 ms 12808 KB Output is correct
14 Correct 703 ms 13068 KB Output is correct
15 Correct 80 ms 8168 KB Output is correct
16 Correct 652 ms 13064 KB Output is correct
17 Correct 744 ms 12760 KB Output is correct
18 Correct 426 ms 11464 KB Output is correct
19 Correct 719 ms 13048 KB Output is correct
20 Correct 514 ms 12808 KB Output is correct
21 Runtime error 418 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -