Submission #200836

#	Time	Username	Problem	Language	Result	Execution time	Memory
200836		balbit	Soccer (JOI17_soccer)	C++14	100 / 100	467 ms	37064 KiB

soccer

#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i=(n-1); i>=0; --i)
#define REP1(i,n) FOR(i,1,n+1)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;


void GG(){cout<<"-1\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b){
    return b==1?1:(mod-mod/b) * inv(mod%b) % mod;
}

const int maxn = 505;

int n, m;
ll A, B, C;
int N;

struct nd{
    ll dst;
    int r,c,tp; // distance, r,c, type
    bool operator < (const nd & oth) const{
        return dst>oth.dst;
    }
};

ll d[maxn][maxn][5]; // 4 is held by player
ll top[maxn][maxn];

signed main(){
    IOS();
    memset(d, 0x3f3f3f3f3f3f3f3f, sizeof (d));
    memset(top, 0x3f3f3f3f3f3f3f3f, sizeof (top));
    cin>>n>>m;
    cin>>A>>B>>C;
    int N; cin>>N;
    vector<pii> pts(N);
    queue<pii> q;
    REP(i,N){
        cin>>pts[i].f>>pts[i].s;
        q.push(pts[i]);
        top[pts[i].f][pts[i].s] = 0;
    }
    static int dx [] = {0,1,0,-1};
    static int dy [] = {1,0,-1,0};
    while (!q.empty()){
        pii v = q.front(); q.pop();
        REP(i,4){
            int r = v.f + dx[i], c = v.s+dy[i];
            if (r>=0&&c>=0&&r<maxn&&c<maxn){
                if (top[r][c]>top[v.f][v.s]+C){
                    top[r][c]=top[v.f][v.s]+C;
                    q.push({r,c});
                }
            }
        }
    }
#ifdef BALBIT
    REP(i,10) REP(j,10) cout<<top[i][j]<<" \n"[j==9];
#endif // BALBIT
    priority_queue<nd> pq;
    d[pts[0].f][pts[0].s][4]=0;
    pq.push({0,pts[0].f,pts[0].s,4});
    while (!pq.empty()){
        nd v = pq.top(); pq.pop();
        int r = v.r, c = v.c, tp = v.tp;
        if (d[r][c][tp]!=v.dst) continue;
//        bug(r,c,v.dst);
        if (tp == 4){
            // Walk directly
            REP(i,4){
                int rr = r + dx[i], cc = c+dy[i];
                if (rr>=0&&cc>=0&&rr<maxn&&cc<maxn){
                    if (d[rr][cc][4] > v.dst + C){
                        d[rr][cc][4] = v.dst + C;
                        pq.push({d[rr][cc][4], rr, cc, 4});
                    }
                }
            }

            REP(i,4){
                if (d[r][c][i] > v.dst + B){
                    d[r][c][i] = v.dst + B;
                    pq.push({d[r][c][i],r,c,i});
                }
            }
        }else{
            if (d[r][c][4] > v.dst + top[r][c]) {
                d[r][c][4] = v.dst + top[r][c];
                pq.push({d[r][c][4],r,c,4});
            }
            int rr = r + dx[tp], cc = c+dy[tp];
            if (rr>=0&&cc>=0&&rr<maxn&&cc<maxn){
                if (d[rr][cc][tp] > v.dst + A){
                    d[rr][cc][tp] = v.dst + A;
                    pq.push({d[rr][cc][tp], rr, cc, tp});
                }
            }
        }
    }
    cout<<d[pts[N-1].f][pts[N-1].s][4]<<endl;
    // Check your array bounds!
    // Think about corner cases (smallest or biggest?)
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:71:45: warning: overflow in implicit constant conversion [-Woverflow]
     memset(d, 0x3f3f3f3f3f3f3f3f, sizeof (d));
                                             ^
soccer.cpp:72:49: warning: overflow in implicit constant conversion [-Woverflow]
     memset(top, 0x3f3f3f3f3f3f3f3f, sizeof (top));
                                                 ^

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65