Submission #1030503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030503		browntoad	Soccer (JOI17_soccer)	C++14	100 / 100	508 ms	123844 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for (int i = (n); i >= 1; i--)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define f first
#define s second
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll maxn = 505;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

ll mpw(ll a, ll p){
    ll ret = 1;
    while(p > 0){
        if (p & 1){
            ret *= a;
            ret %= mod;
        }
        p >>= 1;
        a *= a;
        a %= mod;
    }
    return ret;
}
ll inv(ll a){
    return mpw(a, mod-2);
}

int n, m, a, b, c;

vector<pii> g[3*maxn*maxn];

int hsh(ppi v){
    return v.f.f + v.f.s*n + v.s*n*m;
}
ppi rvhsh(int v){
    return {{v%n, (v/n)%m}, v/(n*m)};
}

vector<int> sp(3*maxn*maxn), occ(3*maxn*maxn);
int dij(int st, int en){
    fill(ALL(sp), inf);
    sp[st] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push({sp[st], st});
    while(SZ(pq)){
        pii tp = pq.top(); pq.pop();
        if (occ[tp.s]) continue;
        occ[tp.s] = 1;
        for (auto y:g[tp.s]){
            if (sp[y.f] > sp[tp.s] + y.s){
                sp[y.f] = sp[tp.s] + y.s;
                pq.push({sp[y.f], y.f});
            }
        }
    }
    return sp[en];
}
void add_edge(int ui, int uj, int uw, int vi, int vj, int vw, int cst, bool doubly){
    int t1 = hsh({{ui, uj}, uw});
    int t2 = hsh({{vi, vj}, vw});
    g[t1].pb({t2, cst});

    /*cout<<ui<<' '<<uj<<' '<<uw<<" -";
    if (!doubly) cout<<">";
    cout<<' '<<vi<<' '<<vj<<' '<<vw<<" with cost "<<cst<<endl;*/

    if (doubly) g[t2].pb({t1, cst});
}

bool dd[maxn][maxn];
int dis[maxn][maxn]; // distance from nearest guy

vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
signed main(){
    IOS();
    cin>>n>>m>>a>>b>>c;
    n++; m++;

    int t; cin>>t;
    pii st, en;
    cin>>st.f>>st.s;
    dd[st.f][st.s] = 1;
    REP(i, t-2){
        pii inter; cin>>inter.f>>inter.s;
        dd[inter.f][inter.s] = 1;
    }
    cin>>en.f>>en.s;
    dd[en.f][en.s] = 1;

    int t1, t2;
    REP(i, n) REP(j, m) {
        add_edge(i, j, 0, i, j, 1, b, 0);
        add_edge(i, j, 0, i, j, 2, b, 0);
    }
    REP(i, n){
        REP(j, m-1){
            add_edge(i, j, 0, i, j+1, 0, c, 1);
            add_edge(i, j, 1, i, j+1, 1, a, 1);
        }
    }
    REP(i, n-1){
        REP(j, m){
            add_edge(i, j, 0, i+1, j, 0, c, 1);
            add_edge(i, j, 2, i+1, j, 2, a, 1);
        }
    }

    queue<pii> qu;
    REP(i, n){
        REP(j, m){
            if (dd[i][j]) {
                dis[i][j] = 0;
                qu.push({i, j});
            }
            else dis[i][j] = inf;
        }
    }
    while(SZ(qu)){
        pii tp = qu.front(); qu.pop();
        pii nw;
        REP(i, 4){
            nw = {tp.f + dx[i], tp.s + dy[i]};
            if (nw.f >= 0 && nw.s >= 0 && nw.f < n && nw.s < m){
                if (!dd[nw.f][nw.s]){
                    dd[nw.f][nw.s] = 1;
                    dis[nw.f][nw.s] = dis[tp.f][tp.s]+c;
                    qu.push({nw.f, nw.s});
                }
            }
        }
    }

    REP(i, n){
        REP(j, m){
            add_edge(i, j, 1, i, j, 0, dis[i][j], 0);
            add_edge(i, j, 2, i, j, 0, dis[i][j], 0);

        }
    }

    int ret = dij(hsh({st, 0}), hsh({en, 0}));
    cout<<ret<<endl;

}
// 42 gg

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:104:9: warning: unused variable 't1' [-Wunused-variable]
  104 |     int t1, t2;
      |         ^~
soccer.cpp:104:13: warning: unused variable 't2' [-Wunused-variable]
  104 |     int t1, t2;
      |             ^~

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