oj.uz

Submission #683154

# Submission time Handle Problem Language Result Execution time Memory
683154 2023-01-17T20:22:47 Z Lobo Soccer (JOI17_soccer) C++17
100 / 100
 508 ms 26500 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;
const int maxh = 505;

int h,w,A,B,C, fat[maxh][maxh], da[maxh][maxh][4], dc[maxh][maxh];
int n, s[maxn], t[maxn];
vector<pair<int,int>> adj = {mp(-1,0),mp(1,0),mp(0,1),mp(0,-1)};

void solve() {
    cin >> h >> w >> A >> B >> C;
    cin >> n;
    for(int i = 0; i <= h; i++) {
        for(int j = 0; j <= w; j++) {
            fat[i][j] = inf;
            da[i][j][0] = da[i][j][1] = da[i][j][2] = da[i][j][3] = dc[i][j] = inf;
        }
    }
    
    queue<pair<int,int>> q;
    for(int i = 1; i <= n; i++) {
        cin >> s[i] >> t[i];
        fat[s[i]][t[i]] = 0;
        q.push(mp(s[i],t[i]));
    }

    while(q.size()) {
        int i = q.front().fr;
        int j = q.front().sc;
        q.pop();
        for(auto X : adj) {
            int i1 = i+X.fr;
            int j1 = j+X.sc;
            if(i1 < 0 || j1 < 0 || i1 > h || j1 > w) continue;
            if(fat[i1][j1] == inf) {
                fat[i1][j1] = fat[i][j]+C;
                q.push(mp(i1,j1));
            }
        }
    } 

    priority_queue<pair<pair<int,pair<int,int>>,pair<int,int>>,vector<pair<pair<int,pair<int,int>>,pair<int,int>>>,greater<pair<pair<int,pair<int,int>>,pair<int,int>>>> pq;
    dc[s[1]][t[1]] = 0;
    pq.push(mp(mp(0,mp(1,0)),mp(s[1],t[1])));
    while(pq.size()) {
        int dist = pq.top().fr.fr;
        int tp = pq.top().fr.sc.fr;
        int tpa = pq.top().fr.sc.sc;
        int i = pq.top().sc.fr;
        int j = pq.top().sc.sc;
        pq.pop();
        if(tp == 0) {
            if(da[i][j][tpa] != dist) continue;
            auto X = adj[tpa];
            int i1 = i+X.fr;
            int j1 = j+X.sc;
            if(!(i1 < 0 || j1 < 0 || i1 > h || j1 > w) && da[i1][j1][tpa] > da[i][j][tpa]+A) {
                da[i1][j1][tpa] = da[i][j][tpa]+A;
                pq.push(mp(mp(da[i1][j1][tpa],mp(0,tpa)),mp(i1,j1)));
            }

            if(fat[i][j] == 0 && dc[i][j] > da[i][j][tpa]) {
                dc[i][j] = da[i][j][tpa];
                pq.push(mp(mp(dc[i][j],mp(1,0)),mp(i,j)));
            }
            if(dc[i][j] > da[i][j][tpa]+fat[i][j]) {
                dc[i][j] = da[i][j][tpa]+fat[i][j];
                pq.push(mp(mp(dc[i][j],mp(1,0)),mp(i,j)));
            }
        }
        else {
            if(dc[i][j] != dist) continue;
            for(auto X : adj) {
                int i1 = i+X.fr;
                int j1 = j+X.sc;
                if(i1 < 0 || j1 < 0 || i1 > h || j1 > w) continue;
                if(dc[i1][j1] > dc[i][j]+C) {
                    dc[i1][j1] = dc[i][j]+C;
                    pq.push(mp(mp(dc[i1][j1],mp(1,0)),mp(i1,j1)));
                }
            }

            for(int dir = 0; dir <= 3; dir++) {
                if(da[i][j][dir] > dc[i][j]+B) {
                    da[i][j][dir] = dc[i][j]+B;
                    pq.push(mp(mp(da[i][j][dir],mp(0,dir)),mp(i,j)));
                }
            }
        }
    }

    cout << dc[s[n]][t[n]] << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8520 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 336 ms 22504 KB Output is correct
4 Correct 365 ms 22580 KB Output is correct
5 Correct 70 ms 7520 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 22732 KB Output is correct
2 Correct 387 ms 22608 KB Output is correct
3 Correct 319 ms 20232 KB Output is correct
4 Correct 277 ms 22588 KB Output is correct
5 Correct 330 ms 22656 KB Output is correct
6 Correct 306 ms 22564 KB Output is correct
7 Correct 380 ms 22732 KB Output is correct
8 Correct 347 ms 22684 KB Output is correct
9 Correct 384 ms 22884 KB Output is correct
10 Correct 60 ms 10308 KB Output is correct
11 Correct 401 ms 22736 KB Output is correct
12 Correct 382 ms 22636 KB Output is correct
13 Correct 233 ms 20272 KB Output is correct
14 Correct 373 ms 22848 KB Output is correct
15 Correct 311 ms 22776 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8520 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 336 ms 22504 KB Output is correct
4 Correct 365 ms 22580 KB Output is correct
5 Correct 70 ms 7520 KB Output is correct
6 Correct 442 ms 22732 KB Output is correct
7 Correct 387 ms 22608 KB Output is correct
8 Correct 319 ms 20232 KB Output is correct
9 Correct 277 ms 22588 KB Output is correct
10 Correct 330 ms 22656 KB Output is correct
11 Correct 306 ms 22564 KB Output is correct
12 Correct 380 ms 22732 KB Output is correct
13 Correct 347 ms 22684 KB Output is correct
14 Correct 384 ms 22884 KB Output is correct
15 Correct 60 ms 10308 KB Output is correct
16 Correct 401 ms 22736 KB Output is correct
17 Correct 382 ms 22636 KB Output is correct
18 Correct 233 ms 20272 KB Output is correct
19 Correct 373 ms 22848 KB Output is correct
20 Correct 311 ms 22776 KB Output is correct
21 Correct 94 ms 7656 KB Output is correct
22 Correct 508 ms 22652 KB Output is correct
23 Correct 418 ms 16452 KB Output is correct
24 Correct 505 ms 17708 KB Output is correct
25 Correct 434 ms 22704 KB Output is correct
26 Correct 431 ms 22984 KB Output is correct
27 Correct 301 ms 15820 KB Output is correct
28 Correct 275 ms 16848 KB Output is correct
29 Correct 393 ms 21320 KB Output is correct
30 Correct 242 ms 16276 KB Output is correct
31 Correct 379 ms 22808 KB Output is correct
32 Correct 467 ms 26500 KB Output is correct
33 Correct 338 ms 22608 KB Output is correct
34 Correct 486 ms 22760 KB Output is correct
35 Correct 213 ms 16264 KB Output is correct