oj.uz

Submission #1007570

# Submission time Handle Problem Language Result Execution time Memory
1007570 2024-06-25T08:01:30 Z dimashhh Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 20820 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);
}
set<pair<ll,pair<int,int>>> st;
int fx,fy;
ll dist[N][N];
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;
            dist[i][j] = 1e17;
        }
    }
    for(int i = 1;i <= f;i++) {
        int s,t;
        cin >> s >> t;
        s++;
        t++;
        if(i == 1){
            dist[s][t] = 0;
            st.insert({0,{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,t] = (*st.begin());
        st.erase(st.begin());
        int x = t.first,y = t.second;
//        cout << x << ' ' << y << ' ' << d << '\n';
        for(int x1 = 1;x1 <= n;x1++){
            ll dd = min(abs(x-x1)*1ll*c+dist[x][y],dist[x][y] + val[x1][y] + abs(x1 - x) * a + (x1 != x ? b : 0));
            if(dd < dist[x1][y]){
                st.erase({dist[x1][y],{x1,y}});
                dist[x1][y] = dd;
                st.insert({dist[x1][y],{x1,y}});
            }
        }
        for(int y1 = 1;y1 <= m;y1++){
            ll dd = min(abs(y-y1)*1ll*c+dist[x][y],dist[x][y]  + val[x][y1] + abs(y - y1) * a + (y1 != y ? b : 0));
            if(dd < dist[x][y1]){
                st.erase({dist[x][y1],{x,y1}});
                dist[x][y1] = dd;
                st.insert({dist[x][y1],{x,y1}});
            }
        }
    }
    cout << dist[fx][fy];
}
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 130 ms 7364 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 721 ms 14728 KB Output is correct
4 Correct 1096 ms 15704 KB Output is correct
5 Correct 145 ms 8900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 18812 KB Output is correct
2 Correct 797 ms 19280 KB Output is correct
3 Correct 563 ms 14928 KB Output is correct
4 Correct 607 ms 13740 KB Output is correct
5 Correct 561 ms 15308 KB Output is correct
6 Correct 594 ms 17492 KB Output is correct
7 Correct 737 ms 20820 KB Output is correct
8 Correct 726 ms 20556 KB Output is correct
9 Correct 727 ms 20564 KB Output is correct
10 Correct 81 ms 7516 KB Output is correct
11 Correct 735 ms 20780 KB Output is correct
12 Correct 738 ms 20048 KB Output is correct
13 Correct 437 ms 15696 KB Output is correct
14 Correct 745 ms 20820 KB Output is correct
15 Correct 530 ms 17556 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 7364 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 721 ms 14728 KB Output is correct
4 Correct 1096 ms 15704 KB Output is correct
5 Correct 145 ms 8900 KB Output is correct
6 Correct 777 ms 18812 KB Output is correct
7 Correct 797 ms 19280 KB Output is correct
8 Correct 563 ms 14928 KB Output is correct
9 Correct 607 ms 13740 KB Output is correct
10 Correct 561 ms 15308 KB Output is correct
11 Correct 594 ms 17492 KB Output is correct
12 Correct 737 ms 20820 KB Output is correct
13 Correct 726 ms 20556 KB Output is correct
14 Correct 727 ms 20564 KB Output is correct
15 Correct 81 ms 7516 KB Output is correct
16 Correct 735 ms 20780 KB Output is correct
17 Correct 738 ms 20048 KB Output is correct
18 Correct 437 ms 15696 KB Output is correct
19 Correct 745 ms 20820 KB Output is correct
20 Correct 530 ms 17556 KB Output is correct
21 Correct 136 ms 8284 KB Output is correct
22 Correct 1018 ms 15952 KB Output is correct
23 Correct 995 ms 16464 KB Output is correct
24 Correct 964 ms 18004 KB Output is correct
25 Correct 714 ms 17540 KB Output is correct
26 Correct 1047 ms 15820 KB Output is correct
27 Correct 614 ms 15828 KB Output is correct
28 Correct 883 ms 16324 KB Output is correct
29 Correct 2904 ms 15500 KB Output is correct
30 Execution timed out 3054 ms 17028 KB Time limit exceeded
31 Halted 0 ms 0 KB -