oj.uz

Submission #683597

# Submission time Handle Problem Language Result Execution time Memory
683597 2023-01-18T20:19:01 Z cadmiumsky Soccer (JOI17_soccer) C++14
0 / 100
 3000 ms 143556 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using tiii = tuple<int,int,int,int>;

const ll inf = 1e13 + 5;
const int nmax = 505;

int H, w;
int A, B, C;

ll mat[nmax][nmax][5];
ll dist[nmax][nmax];

int dirx[4] = {1, -1, 0, 0};
int diry[4] = {0, 0, 1, -1};

signed main() {
  cin >> H >> w;
  cin >> A >> B >> C;
  ++H;
  ++w;
  
  for(int i = 1; i <= H; i++) {
    for(int j = 1; j <= w; j++) {
      dist[i][j] = inf;
      for(int h = 0; h < 5; h++)
        mat[i][j][h] = inf;
    }
  }
  
  int q;
  cin >> q;
  
  int ss = 1, ts = 1, sf = 1, tf = 1; 
  
  queue<pii> que;
  for(int i = 0, x, y; i < q; i++) {
    cin >> x >> y;
    ++x;
    ++y;
    dist[x][y] = 0;
    que.emplace(x, y);
    
    if(i == 0) 
      tie(ss, ts) = pii{x, y};
    tie(sf, tf) = pii{x, y};
  }
  while(!que.empty()) {
    auto [x, y] = que.front();
    que.pop();
    for(int h = 0; h < 4; h++) {
      if(dist[x + dirx[h]][y + diry[h]] > dist[x][y] + C) {
        que.emplace(x + dirx[h], y + diry[h]);
        dist[x + dirx[h]][y + diry[h]] = dist[x][y] + C;
      }
    }
  }
  
  priority_queue<tiii, vector<tiii>, greater<tiii>> heap;
  heap.emplace(0, ss, ts, 4);
  mat[ss][ts][4] = 0;
  while(!heap.empty()) {
    auto [cost, x, y, mode] = heap.top();
    heap.pop();
    //if(mode != 4)
      //cerr << "> " << mat[x][y][mode] << "==" <<  cost << ' ' << x << ' ' << y << ' ' << mode << '\n';
    if(cost > mat[x][y][mode]) continue;
    //if(mode != 4)
      //cerr << cost << ' ' << x << ' ' << y << ' ' << mode << '\n';
    if(mode == 4) {
      for(int h = 0; h < 4; h++) {
        if(mat[x + dirx[h]][y + diry[h]][mode] > mat[x][y][mode] + C) {
          mat[x + dirx[h]][y + diry[h]][mode] = mat[x][y][mode] + C;
          //cerr << "+ " << x + dirx[h] <<  ' ' << y + diry[h] << ' ' << mode << '\n';
          heap.emplace(mat[x][y][mode] + C, x + dirx[h], y + diry[h], mode);
        }
        if(mat[x][y][h] > mat[x][y][mode] + B) {
          //cerr << "+ " << x <<  ' ' << y << ' ' << h << '\n';
          mat[x][y][h] = mat[x][y][mode] + B;
          heap.emplace(mat[x][y][h], x, y, h);
        }
      }
    }
    else {
      if(mat[x + dirx[mode]][y + diry[mode]][mode] > mat[x][y][mode] + A) {
        mat[x + dirx[mode]][y + diry[mode]][mode] = mat[x][y][mode] + A;
          //cerr << "+ " << x + dirx[mode] <<  ' ' << y + diry[mode] << ' ' << mode << '\n';
        heap.emplace(mat[x][y][mode] + A, x + dirx[mode], y + diry[mode], mode);
      }
      if(mat[x][y][4] > mat[x][y][mode] + dist[x][y]) {
        mat[x][y][4] = mat[x][y][mode] + dist[x][y];
        heap.emplace(mat[x][y][4], x, y, 4);      
      }
    }
  }
  ll mn = inf;
  for(int h = 0; h < 5; h++)
    mn = min(mat[sf][tf][h], mn);
  cout << mn << '\n';
}

/**
      Vom spune că toamna a venit... foarte trist -
-- George Bacovia, Scântei galbene
*/

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:58:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     auto [x, y] = que.front();
      |          ^
soccer.cpp:72:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     auto [cost, x, y, mode] = heap.top();
      |          ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Execution timed out 3056 ms 143556 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 78020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Execution timed out 3056 ms 143556 KB Time limit exceeded
4 Halted 0 ms 0 KB -