oj.uz

Submission #670762

# Submission time Handle Problem Language Result Execution time Memory
670762 2022-12-10T10:24:38 Z MohammadAghil Soccer (JOI17_soccer) C++17
100 / 100
 821 ms 16284 KB 
      #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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 4816 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 529 ms 10428 KB Output is correct
4 Correct 511 ms 10496 KB Output is correct
5 Correct 2 ms 4436 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 10508 KB Output is correct
2 Correct 565 ms 10440 KB Output is correct
3 Correct 393 ms 9276 KB Output is correct
4 Correct 439 ms 10564 KB Output is correct
5 Correct 375 ms 10444 KB Output is correct
6 Correct 530 ms 10612 KB Output is correct
7 Correct 547 ms 10568 KB Output is correct
8 Correct 534 ms 10448 KB Output is correct
9 Correct 576 ms 10684 KB Output is correct
10 Correct 60 ms 6072 KB Output is correct
11 Correct 559 ms 10536 KB Output is correct
12 Correct 554 ms 10564 KB Output is correct
13 Correct 319 ms 9312 KB Output is correct
14 Correct 607 ms 10540 KB Output is correct
15 Correct 398 ms 10460 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 4816 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 529 ms 10428 KB Output is correct
4 Correct 511 ms 10496 KB Output is correct
5 Correct 2 ms 4436 KB Output is correct
6 Correct 539 ms 10508 KB Output is correct
7 Correct 565 ms 10440 KB Output is correct
8 Correct 393 ms 9276 KB Output is correct
9 Correct 439 ms 10564 KB Output is correct
10 Correct 375 ms 10444 KB Output is correct
11 Correct 530 ms 10612 KB Output is correct
12 Correct 547 ms 10568 KB Output is correct
13 Correct 534 ms 10448 KB Output is correct
14 Correct 576 ms 10684 KB Output is correct
15 Correct 60 ms 6072 KB Output is correct
16 Correct 559 ms 10536 KB Output is correct
17 Correct 554 ms 10564 KB Output is correct
18 Correct 319 ms 9312 KB Output is correct
19 Correct 607 ms 10540 KB Output is correct
20 Correct 398 ms 10460 KB Output is correct
21 Correct 2 ms 3796 KB Output is correct
22 Correct 643 ms 10540 KB Output is correct
23 Correct 679 ms 14036 KB Output is correct
24 Correct 682 ms 14592 KB Output is correct
25 Correct 623 ms 10464 KB Output is correct
26 Correct 696 ms 14832 KB Output is correct
27 Correct 15 ms 7248 KB Output is correct
28 Correct 779 ms 16284 KB Output is correct
29 Correct 676 ms 11516 KB Output is correct
30 Correct 648 ms 15796 KB Output is correct
31 Correct 589 ms 10556 KB Output is correct
32 Correct 764 ms 15448 KB Output is correct
33 Correct 510 ms 10484 KB Output is correct
34 Correct 821 ms 14636 KB Output is correct
35 Correct 15 ms 6996 KB Output is correct