oj.uz

Submission #1000549

# Submission time Handle Problem Language Result Execution time Memory
1000549 2024-06-17T17:22:13 Z mispertion Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 21960 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 6224 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 759 ms 15676 KB Output is correct
4 Correct 1098 ms 16724 KB Output is correct
5 Correct 189 ms 8528 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 19652 KB Output is correct
2 Correct 888 ms 20592 KB Output is correct
3 Correct 536 ms 15144 KB Output is correct
4 Correct 735 ms 14592 KB Output is correct
5 Correct 625 ms 16204 KB Output is correct
6 Correct 773 ms 18516 KB Output is correct
7 Correct 894 ms 21960 KB Output is correct
8 Correct 772 ms 21840 KB Output is correct
9 Correct 884 ms 21588 KB Output is correct
10 Correct 94 ms 8712 KB Output is correct
11 Correct 847 ms 21844 KB Output is correct
12 Correct 860 ms 21204 KB Output is correct
13 Correct 519 ms 15724 KB Output is correct
14 Correct 799 ms 21928 KB Output is correct
15 Correct 647 ms 18800 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 6224 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 759 ms 15676 KB Output is correct
4 Correct 1098 ms 16724 KB Output is correct
5 Correct 189 ms 8528 KB Output is correct
6 Correct 846 ms 19652 KB Output is correct
7 Correct 888 ms 20592 KB Output is correct
8 Correct 536 ms 15144 KB Output is correct
9 Correct 735 ms 14592 KB Output is correct
10 Correct 625 ms 16204 KB Output is correct
11 Correct 773 ms 18516 KB Output is correct
12 Correct 894 ms 21960 KB Output is correct
13 Correct 772 ms 21840 KB Output is correct
14 Correct 884 ms 21588 KB Output is correct
15 Correct 94 ms 8712 KB Output is correct
16 Correct 847 ms 21844 KB Output is correct
17 Correct 860 ms 21204 KB Output is correct
18 Correct 519 ms 15724 KB Output is correct
19 Correct 799 ms 21928 KB Output is correct
20 Correct 647 ms 18800 KB Output is correct
21 Execution timed out 3033 ms 7524 KB Time limit exceeded
22 Halted 0 ms 0 KB -