oj.uz

Submission #1000553

# Submission time Handle Problem Language Result Execution time Memory
1000553 2024-06-17T17:30:15 Z mispertion Soccer (JOI17_soccer) C++17
35 / 100
 1569 ms 262144 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")

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 214 ms 28848 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 1569 ms 104920 KB Output is correct
4 Correct 1096 ms 55836 KB Output is correct
5 Correct 163 ms 7888 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 12768 KB Output is correct
2 Correct 653 ms 12716 KB Output is correct
3 Correct 451 ms 11468 KB Output is correct
4 Correct 567 ms 12740 KB Output is correct
5 Correct 488 ms 12796 KB Output is correct
6 Correct 617 ms 12748 KB Output is correct
7 Correct 686 ms 13052 KB Output is correct
8 Correct 693 ms 12812 KB Output is correct
9 Correct 691 ms 13068 KB Output is correct
10 Correct 80 ms 8172 KB Output is correct
11 Correct 684 ms 13068 KB Output is correct
12 Correct 657 ms 12760 KB Output is correct
13 Correct 390 ms 11460 KB Output is correct
14 Correct 708 ms 13048 KB Output is correct
15 Correct 538 ms 12812 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 28848 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 1569 ms 104920 KB Output is correct
4 Correct 1096 ms 55836 KB Output is correct
5 Correct 163 ms 7888 KB Output is correct
6 Correct 689 ms 12768 KB Output is correct
7 Correct 653 ms 12716 KB Output is correct
8 Correct 451 ms 11468 KB Output is correct
9 Correct 567 ms 12740 KB Output is correct
10 Correct 488 ms 12796 KB Output is correct
11 Correct 617 ms 12748 KB Output is correct
12 Correct 686 ms 13052 KB Output is correct
13 Correct 693 ms 12812 KB Output is correct
14 Correct 691 ms 13068 KB Output is correct
15 Correct 80 ms 8172 KB Output is correct
16 Correct 684 ms 13068 KB Output is correct
17 Correct 657 ms 12760 KB Output is correct
18 Correct 390 ms 11460 KB Output is correct
19 Correct 708 ms 13048 KB Output is correct
20 Correct 538 ms 12812 KB Output is correct
21 Runtime error 429 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -