oj.uz

Submission #1007695

# Submission time Handle Problem Language Result Execution time Memory
1007695 2024-06-25T10:28:03 Z dimashhh Soccer (JOI17_soccer) C++17
100 / 100
 1272 ms 87492 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 5e2 + 2, MOD = (int)1e9 + 7;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int n,m,d[N][N];
ll val[N][N];
ll a,b,c;
queue<pair<int,int>> q;
bool check(int x,int y){
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
int fx,fy;
ll dist[4][2][N][N];
const ll inf = 1e17;
set<array<ll,5>> st;
void test(){
    cin >> n >> m >> a >> b >> c;
    n++;
    m++;
    int f;cin >> f;
    for(int i = 1;i <= n;i++){ 
        for(int j = 1;j <= m;j++){
            d[i][j] = 1e9;
            for(int dir = 0;dir < 4;dir++)
            {
                dist[dir][0][i][j] = inf;
                dist[dir][1][i][j] = inf;
            }
        }
    }
    for(int i = 1;i <= f;i++) {
        int s,t;
        cin >> s >> t;
        s++;
        t++;
        if(i == 1){
            for(int dir = 0;dir < 4;dir++){
                dist[dir][1][s][t] = 0;
                st.insert({0,dir,1,s,t});
            }
        }
        d[s][t] = 0;
        q.push({s,t});
        fx = s;fy = t;
    }
    while(!q.empty()){
        auto [x,y] = q.front();q.pop();
        val[x][y] = d[x][y] * c;
        for(int i = 0;i < 4;i++){
            int x1 = x + dx[i],y1 = y + dy[i];
            if(check(x1,y1) && d[x1][y1] > d[x][y] + 1){
                d[x1][y1] = d[x][y] +1;
                q.push({x1,y1});
            }
        }
    }
    while(!st.empty())
    {
        auto [D,di,is,x,y] = (*st.begin());
        st.erase(st.begin());
        if(is){
            for(int dir = 0;dir < 4;dir++){
                ll du = D + c;
                int i = x + dx[dir],j = y + dy[dir];
                if(check(i,j) && dist[dir][1][i][j] > du){
                    st.erase({dist[dir][1][i][j],dir,1,i,j});
                    dist[dir][1][i][j] = du;
                    st.insert({du,dir,1,i,j});
                }
                du = D + a + b;
                i = x + dx[dir],j = y + dy[dir];
                if(check(i,j) && dist[dir][0][i][j] > du){
                    st.erase({dist[dir][0][i][j],dir,0,i,j});
                    dist[dir][0][i][j] = du;
                    st.insert({du,dir,0,i,j});
                }
            }
        }
        else{
            int i = x + dx[di],j = y + dy[di];
            ll du = D + a;
            if(check(i,j) && du < dist[di][0][i][j])
            {
                st.erase({dist[di][0][i][j],di,0,i,j});
                dist[di][0][i][j] = du;
                st.insert({dist[di][0][i][j],di,0,i,j});
            }
            du = D + val[x][y];
            if(du < dist[di][1][x][y]){
                st.erase({dist[di][1][x][y],di,1,x,y});
                dist[di][1][x][y] = du;
                st.insert({du,di,1,x,y});
            }
        }
    }
    
    ll res = inf;
    for(int i = 0;i < 4;i++)
    {
        res = min(res,dist[i][0][fx][fy]);
        res = min(res,dist[i][1][fx][fy]);
    }
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        test();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 23636 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 592 ms 33740 KB Output is correct
4 Correct 738 ms 39508 KB Output is correct
5 Correct 112 ms 19288 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 978 ms 65108 KB Output is correct
2 Correct 946 ms 67880 KB Output is correct
3 Correct 525 ms 44624 KB Output is correct
4 Correct 478 ms 30288 KB Output is correct
5 Correct 583 ms 48980 KB Output is correct
6 Correct 462 ms 48136 KB Output is correct
7 Correct 878 ms 87376 KB Output is correct
8 Correct 631 ms 63308 KB Output is correct
9 Correct 978 ms 82260 KB Output is correct
10 Correct 101 ms 26964 KB Output is correct
11 Correct 894 ms 86096 KB Output is correct
12 Correct 997 ms 77360 KB Output is correct
13 Correct 428 ms 44504 KB Output is correct
14 Correct 972 ms 86232 KB Output is correct
15 Correct 688 ms 72644 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 23636 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 592 ms 33740 KB Output is correct
4 Correct 738 ms 39508 KB Output is correct
5 Correct 112 ms 19288 KB Output is correct
6 Correct 978 ms 65108 KB Output is correct
7 Correct 946 ms 67880 KB Output is correct
8 Correct 525 ms 44624 KB Output is correct
9 Correct 478 ms 30288 KB Output is correct
10 Correct 583 ms 48980 KB Output is correct
11 Correct 462 ms 48136 KB Output is correct
12 Correct 878 ms 87376 KB Output is correct
13 Correct 631 ms 63308 KB Output is correct
14 Correct 978 ms 82260 KB Output is correct
15 Correct 101 ms 26964 KB Output is correct
16 Correct 894 ms 86096 KB Output is correct
17 Correct 997 ms 77360 KB Output is correct
18 Correct 428 ms 44504 KB Output is correct
19 Correct 972 ms 86232 KB Output is correct
20 Correct 688 ms 72644 KB Output is correct
21 Correct 147 ms 21584 KB Output is correct
22 Correct 928 ms 37716 KB Output is correct
23 Correct 988 ms 42324 KB Output is correct
24 Correct 1002 ms 40276 KB Output is correct
25 Correct 718 ms 41556 KB Output is correct
26 Correct 746 ms 33808 KB Output is correct
27 Correct 358 ms 20572 KB Output is correct
28 Correct 463 ms 20816 KB Output is correct
29 Correct 658 ms 26456 KB Output is correct
30 Correct 367 ms 20560 KB Output is correct
31 Correct 1154 ms 87492 KB Output is correct
32 Correct 1102 ms 78928 KB Output is correct
33 Correct 533 ms 46932 KB Output is correct
34 Correct 1272 ms 68928 KB Output is correct
35 Correct 402 ms 20572 KB Output is correct