oj.uz

Submission #1026085

# Submission time Handle Problem Language Result Execution time Memory
1026085 2024-07-17T14:16:17 Z phong Soccer (JOI17_soccer) C++17
5 / 100
 520 ms 73972 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define ll long long
//#define int long long
const int nmax = 500 + 5;
const int lg = 18;
const int base = 311;
const int M = 5e6;
const ll oo = 1e18 + 1;
const int mod = 987654321;
#define fi first
#define se second
#define endl "\n"
#define debug(a, m) for(int j = 1; j <= n; ++j) cout << a[j] << ' ';cout << endl;
#define pii pair<ll, int>

using namespace std;

int n, m, q, vis[nmax][nmax];
ll A, B, C;
ll dp[nmax][nmax][3][4];
ll F[nmax][nmax];
struct node{
    ll w;
    int x, y, id, h;
    friend bool operator < (const node&a, const node&b){
        return a.w > b.w;
    }
};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
pii a[nmax];
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m;
    cin >> A >> B >> C;
    cin >> q;
    for(int i = 1, u, v; i <= q; ++i){
        cin >> u >> v;
        a[i]= {u, v};
        vis[u][v] = 1;
    }
    memset(dp, 0x3f, sizeof dp);
    memset(F, 0x3f, sizeof F);
    priority_queue<node> two;
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= m; ++j){
            if(vis[i][j]){
                F[i][j] = 0;
                two.push({F[i][j], i, j});
            }
        }
    }
    while(two.size()){
        node tmp = two.top();two.pop();
        if(tmp.w != F[tmp.x][tmp.y]) continue;
        for(int k = 0; k < 4; ++k){
            int i = dx[k] + tmp.x;
            int j = dy[k] + tmp.y;
            if(i >= 0 && i <= n && j >= 0 && j <= m){
                if(F[i][j] > tmp.w + C){
                    F[i][j] = tmp.w + C;
                    two.push({tmp.w + C, i, j});
                }
            }
        }
    }
    priority_queue<node> one;
    for(int j = 0; j < 4; ++j){
        dp[a[1].fi][a[1].se][0][j] = 0;
        one.push({0, a[1].fi, a[1].se, 0, j});
    }
    while(one.size()){
        node tmp = one.top();one.pop();
        if(tmp.w != dp[tmp.x][tmp.y][tmp.id][tmp.h]) continue;
        if(tmp.id == 0){
            int i = dx[tmp.h] + tmp.x;
            int j = dy[tmp.h] + tmp.y;
            if(i >= 0 && i <= n && j >= 0 && j <= m){
                if(dp[i][j][0][tmp.h] > tmp.w + C){
                    dp[i][j][0][tmp.h] = tmp.w + C;
                    one.push({tmp.w + C, i, j, 0, tmp.h});
                }
            }
            if(dp[tmp.x][tmp.y][tmp.id + 1][tmp.h] > tmp.w){
                dp[tmp.x][tmp.y][tmp.id + 1][tmp.h] = tmp.w;
                one.push({tmp.w, tmp.x, tmp.y, tmp.id + 1, tmp.h});
            }
            for(int k =0; k < 4; ++k){
                if(dp[tmp.x][tmp.y][0][k] > tmp.w){
                    dp[tmp.x][tmp.y][0][k] = tmp.w;
                    one.push({tmp.w, tmp.x, tmp.y, tmp.id, k});

                }
            }
        }
        else{
            if(tmp.id == 1){
                int i = dx[tmp.h] + tmp.x;
                int j = dy[tmp.h] + tmp.y;
                if(i >= 0 && i <= n && j >= 0 && j <= m){
                    if(dp[i][j][1][tmp.h] > tmp.w + A){
                        dp[i][j][1][tmp.h] = tmp.w + A;
                        one.push({tmp.w + A, i, j, 1, tmp.h});
                    }
                }
                if(dp[tmp.x][tmp.y][tmp.id ^ 1][tmp.h] > tmp.w + B + F[tmp.x][tmp.y]){
                    dp[tmp.x][tmp.y][tmp.id ^ 1][tmp.h] = tmp.w + B + F[tmp.x][tmp.y];
                    one.push({tmp.w + F[tmp.x][tmp.y] + B, tmp.x, tmp.y, tmp.id ^ 1, tmp.h});
                }
            }
        }
    }
    ll ans = oo;
//    cout << dp[1][5][0][1] << ' ' << F[1][4];
    for(int i = 0; i < 4; ++i){
        ans = min({ans, dp[a[q].fi][a[q].se][0][i]});
    }
    cout << ans;
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

*/

Compilation message

soccer.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main(){
      | ^~~~
soccer.cpp: In function 'int main()':
soccer.cpp:14:12: warning: narrowing conversion of 'a[1].std::pair<long long int, int>::first' from 'long long int' to 'int' [-Wnarrowing]
   14 | #define fi first
      |            ^
soccer.cpp:77:27: note: in expansion of macro 'fi'
   77 |         one.push({0, a[1].fi, a[1].se, 0, j});
      |                           ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 29664 KB Output is correct
2 Correct 10 ms 26204 KB Output is correct
3 Correct 396 ms 32624 KB Output is correct
4 Correct 463 ms 38880 KB Output is correct
5 Correct 87 ms 26712 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 51244 KB Output is correct
2 Correct 520 ms 51828 KB Output is correct
3 Correct 369 ms 39096 KB Output is correct
4 Correct 368 ms 33000 KB Output is correct
5 Correct 377 ms 39544 KB Output is correct
6 Runtime error 425 ms 73972 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 29664 KB Output is correct
2 Correct 10 ms 26204 KB Output is correct
3 Correct 396 ms 32624 KB Output is correct
4 Correct 463 ms 38880 KB Output is correct
5 Correct 87 ms 26712 KB Output is correct
6 Correct 516 ms 51244 KB Output is correct
7 Correct 520 ms 51828 KB Output is correct
8 Correct 369 ms 39096 KB Output is correct
9 Correct 368 ms 33000 KB Output is correct
10 Correct 377 ms 39544 KB Output is correct
11 Runtime error 425 ms 73972 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -