Submission #670762

#	Time	Username	Problem	Language	Result	Execution time	Memory
670762		MohammadAghil	Soccer (JOI17_soccer)	C++17	100 / 100	821 ms	16284 KiB

soccer

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 500 + 5, lg = 22, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
ll dist[maxn][maxn][2], near[maxn][maxn];

int main(){ IOS();
     int n, m; cin >> n >> m;
     ll a, b, c; cin >> a >> b >> c;
     int k; cin >> k; k--;
     rep(i,0,n+1) rep(j,0,m+1){
          dist[i][j][0] = dist[i][j][1] = near[i][j] = inf;
     }
     deque<pp> dq;
     rep(i,0,k){
          int x, y; cin >> x >> y;
          if(near[x][y] == 0) continue;
          dq.pb({x, y});
          near[x][y] = 0;
     } 
     int sb = dq[0].ff, eb = dq[0].ss;
     int s, e; cin >> s >> e;

     if(c <= a){
          cout << 1ll*(abs(sb - s) + abs(eb - e))*c << '\n';
          return 0;
     }

     while(sz(dq)){
          auto[x, y] = dq.front(); dq.pop_front();
          rep(d,0,4){
               int r = x + dx[d], c = y + dy[d];
               if(r < 0 || r > n || c < 0 || c > m || near[r][c] - inf) continue;
               near[r][c] = near[x][y] + 1;
               dq.pb({r, c});
          }
     }
     rep(i,0,n+1) rep(j,0,m+1) {
          near[i][j] *= c;
          // er(i, j, near[i][j]);
     }
     priority_queue<pair<ll, pp>, vector<pair<ll, pp>>, greater<pair<ll, pp>>> q;
     q.push({dist[sb][eb][0] = 0, {sb<<1, eb}});
     while(sz(q)){
          auto[w, p] = q.top(); q.pop();
          auto[xx, y] = p;
          int x = xx>>1;
          bool is = xx&1;
          if(dist[x][y][is] - w) continue;
          if(is){
               if(dist[x][y][0] > w){
                    q.push({dist[x][y][0] = w, {x<<1, y}});
               }
               ll dd = w + c;
               rep(d,0,4){
                    int r = x + dx[d], c = y + dy[d];
                    if(r < 0 || r > n || c < 0 || c > m || dist[r][c][1] <= dd) continue;
                    q.push({dist[r][c][1] = dd, {r<<1|1, c}});
               }
               rep(i,0,n+1){
                    dd = w + abs(x - i)*a + b;
                    if(dd < dist[i][y][0]){
                         q.push({dist[i][y][0] = dd, {i<<1, y}});
                    }
               }
               rep(i,0,m+1){
                    dd = w + abs(y - i)*a + b;
                    if(dd < dist[x][i][0]){
                         q.push({dist[x][i][0] = dd, {x<<1, i}});
                    }
               }
          }else{
               ll d = w + near[x][y];
               if(d < dist[x][y][1]){
                    q.push({dist[x][y][1] = d, {x<<1|1, y}});
               }
          }
     }

     cout << dist[s][e][0] << '\n';
}

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