oj.uz

Submission #1007605

# Submission time Handle Problem Language Result Execution time Memory
1007605 2024-06-25T09:12:15 Z dimashhh Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 32672 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 = 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}});
            }
        }
        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 = 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}});
            }
        }
        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 10832 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 477 ms 30868 KB Output is correct
4 Correct 903 ms 31060 KB Output is correct
5 Correct 130 ms 14164 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 32340 KB Output is correct
2 Correct 428 ms 32248 KB Output is correct
3 Correct 402 ms 26004 KB Output is correct
4 Correct 370 ms 30292 KB Output is correct
5 Correct 361 ms 26452 KB Output is correct
6 Correct 453 ms 30676 KB Output is correct
7 Correct 370 ms 32596 KB Output is correct
8 Correct 554 ms 31684 KB Output is correct
9 Correct 360 ms 32600 KB Output is correct
10 Correct 37 ms 9812 KB Output is correct
11 Correct 410 ms 32588 KB Output is correct
12 Correct 439 ms 32596 KB Output is correct
13 Correct 336 ms 25384 KB Output is correct
14 Correct 404 ms 32672 KB Output is correct
15 Correct 270 ms 27220 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 10832 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 477 ms 30868 KB Output is correct
4 Correct 903 ms 31060 KB Output is correct
5 Correct 130 ms 14164 KB Output is correct
6 Correct 457 ms 32340 KB Output is correct
7 Correct 428 ms 32248 KB Output is correct
8 Correct 402 ms 26004 KB Output is correct
9 Correct 370 ms 30292 KB Output is correct
10 Correct 361 ms 26452 KB Output is correct
11 Correct 453 ms 30676 KB Output is correct
12 Correct 370 ms 32596 KB Output is correct
13 Correct 554 ms 31684 KB Output is correct
14 Correct 360 ms 32600 KB Output is correct
15 Correct 37 ms 9812 KB Output is correct
16 Correct 410 ms 32588 KB Output is correct
17 Correct 439 ms 32596 KB Output is correct
18 Correct 336 ms 25384 KB Output is correct
19 Correct 404 ms 32672 KB Output is correct
20 Correct 270 ms 27220 KB Output is correct
21 Correct 153 ms 13904 KB Output is correct
22 Correct 843 ms 31568 KB Output is correct
23 Correct 785 ms 29520 KB Output is correct
24 Correct 648 ms 32008 KB Output is correct
25 Correct 616 ms 30544 KB Output is correct
26 Correct 921 ms 31060 KB Output is correct
27 Correct 493 ms 30424 KB Output is correct
28 Correct 772 ms 31432 KB Output is correct
29 Correct 2764 ms 30872 KB Output is correct
30 Execution timed out 3082 ms 20420 KB Time limit exceeded
31 Halted 0 ms 0 KB -