Submission #118161

#	Time	Username	Problem	Language	Result	Execution time	Memory
118161		JohnTitor	Soccer (JOI17_soccer)	C++11	100 / 100	305 ms	20360 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Soccer"
int h, w, n;
ll a, b, c;
int s, t;
int p, q;
ll g[501][501];
bool done[501][501];
const int cx[]={0, 1, 0, -1, 0};
const int cy[]={0, 0, -1, 0, 1};
ll f[501][501][5];///0=player with ball, 1234=ball moving without player
class obj{
public:
    int x, y, d;
    ll cost;
    obj(int x, int y, int d, ll cost){
        this->x=x;
        this->y=y;
        this->d=d;
        this->cost=cost;
    }
};
class cmp{
public:
    bool operator ()(obj A, obj B){
        return A.cost>B.cost;
    }
};
priority_queue <obj, vector <obj>, cmp> heap;
queue <pair <int, int>> que;
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(h);
    read(w);
    read(a);
    read(b);
    read(c);
    read(n);
    {
        int x, y;
        FOR(i, 1, n){
            read(x);
            read(y);
            que.push(mp(x, y));
            done[x][y]=1;
            if(i==1){
                s=x;
                t=y;
            }
            g[x][y]=0;
        }
        p=x;
        q=y;
    }
    while(!que.empty()){
        auto p=que.front();
        que.pop();
        FOR(i, 1, 4){
            int xx=p.first+cx[i];
            int yy=p.second+cy[i];
            if(xx<0||xx>h) continue;
            if(yy<0||yy>w) continue;
            if(done[xx][yy]) continue;
            done[xx][yy]=1;
            g[xx][yy]=g[p.first][p.second]+c;
            que.push(mp(xx, yy));
        }
    }
//    FOR(i, 0, h) FOR(j, 0, w) cerr<<g[i][j]<<" \n"[j==w];
    FOR(i, 0, h) FOR(j, 0, w) FOR(d, 0, 4) f[i][j][d]=1e18;
    f[s][t][0]=0;
    heap.push(obj(s, t, 0, 0));
    while(!heap.empty()){
        obj o=heap.top();
        heap.pop();
        if(o.cost>f[o.x][o.y][o.d]) continue;
//        cerr<<o.x<<' '<<o.y<<' '<<o.d<<' '<<o.cost<<'\n';
        if(o.x==p&&o.y==q&&o.d==0) break;
        if(o.d){///moving
            ///stop
            if(f[o.x][o.y][0]>o.cost+g[o.x][o.y]){
                f[o.x][o.y][0]=o.cost+g[o.x][o.y];
                heap.push(obj(o.x, o.y, 0, f[o.x][o.y][0]));
            }
            ///continue
            int xx=o.x+cx[o.d];
            int yy=o.y+cy[o.d];
            if(0<=xx&&xx<=h&&0<=yy&&yy<=w){
                if(f[xx][yy][o.d]>o.cost+a){
                    f[xx][yy][o.d]=o.cost+a;
                    heap.push(obj(xx, yy, o.d, f[xx][yy][o.d]));
                }
            }
        }
        else{
            FOR(i, 1, 4){///kick
                if(f[o.x][o.y][i]>o.cost+b){
                    f[o.x][o.y][i]=o.cost+b;
                    heap.push(obj(o.x, o.y, i, f[o.x][o.y][i]));
                }
            }
            ///move with ball
            FOR(i, 1, 4){
                int xx=o.x+cx[i];
                int yy=o.y+cy[i];
                if(0<=xx&&xx<=h&&0<=yy&&yy<=w){
                    if(f[xx][yy][0]>o.cost+c){
                        f[xx][yy][0]=o.cost+c;
                        heap.push(obj(xx, yy, 0, f[xx][yy][0]));
                    }
                }
            }
        }
    }
    writeln(f[p][q][0]);
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:73:10: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
         q=y;
         ~^~
soccer.cpp:72:10: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
         p=x;
         ~^~

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