oj.uz

Submission #1000552

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

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 101 ms 6488 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 631 ms 15752 KB Output is correct
4 Correct 1067 ms 16980 KB Output is correct
5 Correct 169 ms 8532 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 19892 KB Output is correct
2 Correct 763 ms 20816 KB Output is correct
3 Correct 493 ms 15180 KB Output is correct
4 Correct 575 ms 14828 KB Output is correct
5 Correct 495 ms 16208 KB Output is correct
6 Correct 668 ms 18768 KB Output is correct
7 Correct 800 ms 21960 KB Output is correct
8 Correct 681 ms 21840 KB Output is correct
9 Correct 805 ms 21456 KB Output is correct
10 Correct 87 ms 8824 KB Output is correct
11 Correct 785 ms 21784 KB Output is correct
12 Correct 745 ms 21100 KB Output is correct
13 Correct 477 ms 15788 KB Output is correct
14 Correct 800 ms 21856 KB Output is correct
15 Correct 583 ms 18772 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 6488 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 631 ms 15752 KB Output is correct
4 Correct 1067 ms 16980 KB Output is correct
5 Correct 169 ms 8532 KB Output is correct
6 Correct 714 ms 19892 KB Output is correct
7 Correct 763 ms 20816 KB Output is correct
8 Correct 493 ms 15180 KB Output is correct
9 Correct 575 ms 14828 KB Output is correct
10 Correct 495 ms 16208 KB Output is correct
11 Correct 668 ms 18768 KB Output is correct
12 Correct 800 ms 21960 KB Output is correct
13 Correct 681 ms 21840 KB Output is correct
14 Correct 805 ms 21456 KB Output is correct
15 Correct 87 ms 8824 KB Output is correct
16 Correct 785 ms 21784 KB Output is correct
17 Correct 745 ms 21100 KB Output is correct
18 Correct 477 ms 15788 KB Output is correct
19 Correct 800 ms 21856 KB Output is correct
20 Correct 583 ms 18772 KB Output is correct
21 Execution timed out 3034 ms 7508 KB Time limit exceeded
22 Halted 0 ms 0 KB -