oj.uz

Submission #1007662

# Submission time Handle Problem Language Result Execution time Memory
1007662 2024-06-25T09:54:37 Z dimashhh Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 20928 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];
set<int> R[N],C[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});
            }
        }
    }
    for(int i = 1;i <= n;i++){
        R[i].insert(-m);
        R[i].insert(m + m);
    }
    for(int i = 1;i <= m;i++){
        C[i].insert(-n);
        C[i].insert(n + n);
    }
    while(!st.empty()){
        auto [d,t] = (*st.begin());
        st.erase(st.begin());
        int x = t.first,y = t.second;
        for(int dir =0 ;dir < 4;dir++){
            int nx = x +dx[dir],ny = y + dy[dir];
            ll du = d + c;
            if(check(nx,ny) && dist[nx][ny] > du){
                st.erase({dist[nx][ny],{nx,ny}});
                dist[nx][ny] = du;
                st.insert({dist[nx][ny],{nx,ny}});
            }
        }
        for(int x1 = 1;x1 <= n;x1++){
            ll dd = dist[x][y] + val[x1][y] + abs(x1 - x) * a + b;
            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 = dist[x][y] + val[x][y1] + abs(y1 - y) * a + b;
            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 84 ms 7464 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 548 ms 14872 KB Output is correct
4 Correct 889 ms 15952 KB Output is correct
5 Correct 139 ms 9044 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 18760 KB Output is correct
2 Correct 639 ms 19536 KB Output is correct
3 Correct 428 ms 15188 KB Output is correct
4 Correct 500 ms 13876 KB Output is correct
5 Correct 418 ms 15368 KB Output is correct
6 Correct 569 ms 17748 KB Output is correct
7 Correct 650 ms 20816 KB Output is correct
8 Correct 577 ms 20880 KB Output is correct
9 Correct 670 ms 20708 KB Output is correct
10 Correct 60 ms 7772 KB Output is correct
11 Correct 623 ms 20928 KB Output is correct
12 Correct 631 ms 20024 KB Output is correct
13 Correct 372 ms 15956 KB Output is correct
14 Correct 602 ms 20816 KB Output is correct
15 Correct 447 ms 17748 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7464 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 548 ms 14872 KB Output is correct
4 Correct 889 ms 15952 KB Output is correct
5 Correct 139 ms 9044 KB Output is correct
6 Correct 622 ms 18760 KB Output is correct
7 Correct 639 ms 19536 KB Output is correct
8 Correct 428 ms 15188 KB Output is correct
9 Correct 500 ms 13876 KB Output is correct
10 Correct 418 ms 15368 KB Output is correct
11 Correct 569 ms 17748 KB Output is correct
12 Correct 650 ms 20816 KB Output is correct
13 Correct 577 ms 20880 KB Output is correct
14 Correct 670 ms 20708 KB Output is correct
15 Correct 60 ms 7772 KB Output is correct
16 Correct 623 ms 20928 KB Output is correct
17 Correct 631 ms 20024 KB Output is correct
18 Correct 372 ms 15956 KB Output is correct
19 Correct 602 ms 20816 KB Output is correct
20 Correct 447 ms 17748 KB Output is correct
21 Execution timed out 3036 ms 8304 KB Time limit exceeded
22 Halted 0 ms 0 KB -