oj.uz

Submission #1000546

# Submission time Handle Problem Language Result Execution time Memory
1000546 2024-06-17T17:15:02 Z mispertion Soccer (JOI17_soccer) C++14
35 / 100
 1626 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 209 ms 28832 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 1626 ms 105020 KB Output is correct
4 Correct 1085 ms 55688 KB Output is correct
5 Correct 159 ms 7892 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 12612 KB Output is correct
2 Correct 659 ms 12796 KB Output is correct
3 Correct 448 ms 11464 KB Output is correct
4 Correct 611 ms 12776 KB Output is correct
5 Correct 497 ms 12796 KB Output is correct
6 Correct 687 ms 12756 KB Output is correct
7 Correct 707 ms 13052 KB Output is correct
8 Correct 643 ms 12812 KB Output is correct
9 Correct 717 ms 13064 KB Output is correct
10 Correct 80 ms 8172 KB Output is correct
11 Correct 733 ms 13064 KB Output is correct
12 Correct 664 ms 12768 KB Output is correct
13 Correct 424 ms 11472 KB Output is correct
14 Correct 690 ms 13048 KB Output is correct
15 Correct 526 ms 12812 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 28832 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 1626 ms 105020 KB Output is correct
4 Correct 1085 ms 55688 KB Output is correct
5 Correct 159 ms 7892 KB Output is correct
6 Correct 652 ms 12612 KB Output is correct
7 Correct 659 ms 12796 KB Output is correct
8 Correct 448 ms 11464 KB Output is correct
9 Correct 611 ms 12776 KB Output is correct
10 Correct 497 ms 12796 KB Output is correct
11 Correct 687 ms 12756 KB Output is correct
12 Correct 707 ms 13052 KB Output is correct
13 Correct 643 ms 12812 KB Output is correct
14 Correct 717 ms 13064 KB Output is correct
15 Correct 80 ms 8172 KB Output is correct
16 Correct 733 ms 13064 KB Output is correct
17 Correct 664 ms 12768 KB Output is correct
18 Correct 424 ms 11472 KB Output is correct
19 Correct 690 ms 13048 KB Output is correct
20 Correct 526 ms 12812 KB Output is correct
21 Runtime error 420 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -