oj.uz

Submission #200836

# Submission time Handle Problem Language Result Execution time Memory
200836 2020-02-08T09:25:58 Z balbit Soccer (JOI17_soccer) C++14
100 / 100
 467 ms 37064 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 18620 KB Output is correct
2 Correct 264 ms 37064 KB Output is correct
3 Correct 312 ms 18788 KB Output is correct
4 Correct 328 ms 18664 KB Output is correct
5 Correct 147 ms 12664 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 18664 KB Output is correct
2 Correct 326 ms 18680 KB Output is correct
3 Correct 324 ms 18672 KB Output is correct
4 Correct 249 ms 18660 KB Output is correct
5 Correct 333 ms 18680 KB Output is correct
6 Correct 265 ms 18660 KB Output is correct
7 Correct 328 ms 18708 KB Output is correct
8 Correct 314 ms 18708 KB Output is correct
9 Correct 332 ms 24840 KB Output is correct
10 Correct 327 ms 18704 KB Output is correct
11 Correct 324 ms 18708 KB Output is correct
12 Correct 331 ms 18684 KB Output is correct
13 Correct 260 ms 18664 KB Output is correct
14 Correct 324 ms 18708 KB Output is correct
15 Correct 321 ms 18708 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 18620 KB Output is correct
2 Correct 264 ms 37064 KB Output is correct
3 Correct 312 ms 18788 KB Output is correct
4 Correct 328 ms 18664 KB Output is correct
5 Correct 147 ms 12664 KB Output is correct
6 Correct 348 ms 18664 KB Output is correct
7 Correct 326 ms 18680 KB Output is correct
8 Correct 324 ms 18672 KB Output is correct
9 Correct 249 ms 18660 KB Output is correct
10 Correct 333 ms 18680 KB Output is correct
11 Correct 265 ms 18660 KB Output is correct
12 Correct 328 ms 18708 KB Output is correct
13 Correct 314 ms 18708 KB Output is correct
14 Correct 332 ms 24840 KB Output is correct
15 Correct 327 ms 18704 KB Output is correct
16 Correct 324 ms 18708 KB Output is correct
17 Correct 331 ms 18684 KB Output is correct
18 Correct 260 ms 18664 KB Output is correct
19 Correct 324 ms 18708 KB Output is correct
20 Correct 321 ms 18708 KB Output is correct
21 Correct 200 ms 13944 KB Output is correct
22 Correct 447 ms 18748 KB Output is correct
23 Correct 467 ms 18680 KB Output is correct
24 Correct 453 ms 15656 KB Output is correct
25 Correct 409 ms 18684 KB Output is correct
26 Correct 401 ms 18852 KB Output is correct
27 Correct 239 ms 14456 KB Output is correct
28 Correct 224 ms 15096 KB Output is correct
29 Correct 360 ms 17780 KB Output is correct
30 Correct 194 ms 14968 KB Output is correct
31 Correct 366 ms 18704 KB Output is correct
32 Correct 458 ms 20848 KB Output is correct
33 Correct 298 ms 18660 KB Output is correct
34 Correct 461 ms 18704 KB Output is correct
35 Correct 158 ms 14712 KB Output is correct