oj.uz

Submission #398741

# Submission time Handle Problem Language Result Execution time Memory
398741 2021-05-04T19:02:51 Z duality Soccer (JOI17_soccer) C++11
100 / 100
 577 ms 21552 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int dx[4] = {-1,0,1,0},dy[4] = {0,-1,0,1};
int S[100000],T[100000];
int dist[501][501];
queue<pii> Q;
LLI dist2[501][501][6];
priority_queue<pair<LLI,pair<pii,int> > > HH;
int main() {
    int i;
    int H,W,A,B,C,N;
    scanf("%d %d %d %d %d %d",&H,&W,&A,&B,&C,&N);
    for (i = 0; i < N; i++) scanf("%d %d",&S[i],&T[i]);

    int j,k;
    for (i = 0; i <= H; i++) {
        for (j = 0; j <= W; j++) dist[i][j] = -1;
    }
    for (i = 0; i < N; i++) {
        dist[S[i]][T[i]] = 0;
        Q.push(mp(S[i],T[i]));
    }
    while (!Q.empty()) {
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();

        for (i = 0; i < 4; i++) {
            int xx = x+dx[i],yy = y+dy[i];
            if ((xx >= 0) && (xx <= W) && (yy >= 0) && (yy <= H) && (dist[yy][xx] == -1)) {
                dist[yy][xx] = dist[y][x]+1;
                Q.push(mp(yy,xx));
            }
        }
    }
    for (i = 0; i <= H; i++) {
        for (j = 0; j <= W; j++) {
            for (k = 0; k < 6; k++) dist2[i][j][k] = -1;
        }
    }
    dist2[S[0]][T[0]][1] = 0,HH.push(mp(0,mp(mp(S[0],T[0]),1)));
    while (!HH.empty()) {
        LLI d = -HH.top().first;
        int y = HH.top().second.first.first;
        int x = HH.top().second.first.second;
        int s = HH.top().second.second;
        HH.pop();

        if (d > dist2[y][x][s]) continue;
        if (s == 0) {
            if ((dist2[y][x][1] == -1) || (d+(LLI) C*dist[y][x] < dist2[y][x][1])) {
                dist2[y][x][1] = d+(LLI) C*dist[y][x];
                HH.push(mp(-dist2[y][x][1],mp(mp(y,x),1)));
            }
        }
        else if (s == 1) {
            for (i = 0; i < 4; i++) {
                int xx = x+dx[i],yy = y+dy[i];
                if ((xx >= 0) && (xx <= W) && (yy >= 0) && (yy <= H)) {
                    if ((dist2[yy][xx][1] == -1) || (d+C < dist2[yy][xx][1])) {
                        dist2[yy][xx][1] = d+C;
                        HH.push(mp(-dist2[yy][xx][1],mp(mp(yy,xx),1)));
                    }
                }
                if ((dist2[y][x][i+2] == -1) || (d+B < dist2[y][x][i+2])) {
                    dist2[y][x][i+2] = d+B;
                    HH.push(mp(-dist2[y][x][i+2],mp(mp(y,x),i+2)));
                }
            }
        }
        else {
            if ((dist2[y][x][0] == -1) || (d < dist2[y][x][0])) {
                dist2[y][x][0] = d;
                HH.push(mp(-dist2[y][x][0],mp(mp(y,x),0)));
            }
            int xx = x+dx[s-2],yy = y+dy[s-2];
            if ((xx >= 0) && (xx <= W) && (yy >= 0) && (yy <= H)) {
                if ((dist2[yy][xx][s] == -1) || (d+A < dist2[yy][xx][s])) {
                    dist2[yy][xx][s] = d+A;
                    HH.push(mp(-dist2[yy][xx][s],mp(mp(yy,xx),s)));
                }
            }
        }
    }
    printf("%lld\n",min(dist2[S[N-1]][T[N-1]][0],dist2[S[N-1]][T[N-1]][1]));

    return 0;
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d %d %d %d %d %d",&H,&W,&A,&B,&C,&N);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:68:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     for (i = 0; i < N; i++) scanf("%d %d",&S[i],&T[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 6576 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 387 ms 19304 KB Output is correct
4 Correct 394 ms 19340 KB Output is correct
5 Correct 102 ms 6732 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 19388 KB Output is correct
2 Correct 442 ms 19376 KB Output is correct
3 Correct 345 ms 16856 KB Output is correct
4 Correct 339 ms 19332 KB Output is correct
5 Correct 341 ms 19000 KB Output is correct
6 Correct 363 ms 19332 KB Output is correct
7 Correct 441 ms 19432 KB Output is correct
8 Correct 403 ms 19384 KB Output is correct
9 Correct 462 ms 19432 KB Output is correct
10 Correct 74 ms 6864 KB Output is correct
11 Correct 443 ms 19492 KB Output is correct
12 Correct 456 ms 19404 KB Output is correct
13 Correct 280 ms 16824 KB Output is correct
14 Correct 439 ms 19400 KB Output is correct
15 Correct 362 ms 19076 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 6576 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 387 ms 19304 KB Output is correct
4 Correct 394 ms 19340 KB Output is correct
5 Correct 102 ms 6732 KB Output is correct
6 Correct 456 ms 19388 KB Output is correct
7 Correct 442 ms 19376 KB Output is correct
8 Correct 345 ms 16856 KB Output is correct
9 Correct 339 ms 19332 KB Output is correct
10 Correct 341 ms 19000 KB Output is correct
11 Correct 363 ms 19332 KB Output is correct
12 Correct 441 ms 19432 KB Output is correct
13 Correct 403 ms 19384 KB Output is correct
14 Correct 462 ms 19432 KB Output is correct
15 Correct 74 ms 6864 KB Output is correct
16 Correct 443 ms 19492 KB Output is correct
17 Correct 456 ms 19404 KB Output is correct
18 Correct 280 ms 16824 KB Output is correct
19 Correct 439 ms 19400 KB Output is correct
20 Correct 362 ms 19076 KB Output is correct
21 Correct 119 ms 6824 KB Output is correct
22 Correct 529 ms 19324 KB Output is correct
23 Correct 490 ms 15068 KB Output is correct
24 Correct 577 ms 16464 KB Output is correct
25 Correct 469 ms 19384 KB Output is correct
26 Correct 508 ms 19564 KB Output is correct
27 Correct 380 ms 15052 KB Output is correct
28 Correct 338 ms 15628 KB Output is correct
29 Correct 484 ms 18480 KB Output is correct
30 Correct 305 ms 15468 KB Output is correct
31 Correct 454 ms 19400 KB Output is correct
32 Correct 570 ms 21552 KB Output is correct
33 Correct 372 ms 19340 KB Output is correct
34 Correct 566 ms 19432 KB Output is correct
35 Correct 299 ms 15428 KB Output is correct