oj.uz

Submission #1007608

# Submission time Handle Problem Language Result Execution time Memory
1007608 2024-06-25T09:20:16 Z dimashhh Soccer (JOI17_soccer) C++17
30 / 100
 407 ms 32648 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;
        int l,r;
        auto it = C[y].lower_bound(x);
        r = (x + (*it)) / 2 + 1;
        it--;
        l = (x +(*it)) / 2 - 1;
        for(int x1 = max(1,l);x1 <= min(n,r);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}});
            }
        }
        it = R[x].lower_bound(y);
        r = (y + (*it)) / 2 + 1;
        it--;
        l = (y +(*it)) / 2 - 1;
        for(int y1 = max(1,l);y1 <= min(m,r);y1++){
            ll dd = dist[x][y]  + val[x][y1] + abs(y - y1) * 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}});
            }
        }
        R[x].insert(y);
        C[y].insert(x);
    }
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 11088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 32392 KB Output is correct
2 Correct 295 ms 32396 KB Output is correct
3 Correct 234 ms 25936 KB Output is correct
4 Correct 320 ms 30292 KB Output is correct
5 Correct 227 ms 26452 KB Output is correct
6 Correct 407 ms 30544 KB Output is correct
7 Correct 267 ms 32584 KB Output is correct
8 Correct 343 ms 31568 KB Output is correct
9 Correct 240 ms 32648 KB Output is correct
10 Correct 28 ms 9740 KB Output is correct
11 Correct 250 ms 32596 KB Output is correct
12 Correct 261 ms 32596 KB Output is correct
13 Correct 280 ms 25440 KB Output is correct
14 Correct 242 ms 32596 KB Output is correct
15 Correct 193 ms 27216 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 11088 KB Output isn't correct
2 Halted 0 ms 0 KB -