oj.uz

Submission #1000543

# Submission time Handle Problem Language Result Execution time Memory
1000543 2024-06-17T17:05:00 Z mispertion Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 22120 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;
    set<pair<int, pii>> st;
    st.insert({0, {si, sj}});
    while(!st.empty()){
        int vi = st.begin()->S.F, vj = st.begin()->S.S;
        st.erase(st.begin());
        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){
                st.erase({d[ni][nj], {ni, nj}});
                d[ni][nj] = d[vi][vj] + c;
                st.insert({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)){
                st.erase({d[i][vj], {i, vj}});
                d[i][vj] = (d[vi][vj] + mnd[i][vj] * c + a * abs(i - vi) + b);
                st.insert({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)){
                st.erase({d[vi][j], {vi, j}});
                d[vi][j] = (d[vi][vj] + mnd[vi][j] * c + a * abs(j - vj) + b);
                st.insert({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 107 ms 6232 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 755 ms 15764 KB Output is correct
4 Correct 1147 ms 16880 KB Output is correct
5 Correct 185 ms 8424 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 19792 KB Output is correct
2 Correct 819 ms 20568 KB Output is correct
3 Correct 542 ms 14928 KB Output is correct
4 Correct 681 ms 14932 KB Output is correct
5 Correct 576 ms 16216 KB Output is correct
6 Correct 706 ms 18516 KB Output is correct
7 Correct 852 ms 21928 KB Output is correct
8 Correct 760 ms 21660 KB Output is correct
9 Correct 852 ms 21568 KB Output is correct
10 Correct 95 ms 8796 KB Output is correct
11 Correct 882 ms 22120 KB Output is correct
12 Correct 829 ms 21072 KB Output is correct
13 Correct 497 ms 15700 KB Output is correct
14 Correct 842 ms 21844 KB Output is correct
15 Correct 630 ms 18660 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 6232 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 755 ms 15764 KB Output is correct
4 Correct 1147 ms 16880 KB Output is correct
5 Correct 185 ms 8424 KB Output is correct
6 Correct 806 ms 19792 KB Output is correct
7 Correct 819 ms 20568 KB Output is correct
8 Correct 542 ms 14928 KB Output is correct
9 Correct 681 ms 14932 KB Output is correct
10 Correct 576 ms 16216 KB Output is correct
11 Correct 706 ms 18516 KB Output is correct
12 Correct 852 ms 21928 KB Output is correct
13 Correct 760 ms 21660 KB Output is correct
14 Correct 852 ms 21568 KB Output is correct
15 Correct 95 ms 8796 KB Output is correct
16 Correct 882 ms 22120 KB Output is correct
17 Correct 829 ms 21072 KB Output is correct
18 Correct 497 ms 15700 KB Output is correct
19 Correct 842 ms 21844 KB Output is correct
20 Correct 630 ms 18660 KB Output is correct
21 Execution timed out 3089 ms 7348 KB Time limit exceeded
22 Halted 0 ms 0 KB -