oj.uz

답안 #479563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
479563 2021-10-12T07:28:19 Z Neos Patkice II (COCI21_patkice2) C++14
110 / 110
 1304 ms 107756 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
 
#define task "test"
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i, l, r) for( ll i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( ll i = (r) ; i >= (l) ; i-- )
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';
 
const int N = 2e3 + 7;
const ll inf = 0x3f3f3f3f;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int n, m, d[N][N];
ii st, des, tr[N][N];
char ch[N][N];

int get(char ch) {
  if (ch == '^') return 0;
  if (ch == '<') return 1;
  if (ch == 'v') return 2;
  if (ch == '>') return 3;
  return -1;
}

int getindx(ii x, ii y) {
  forw(i, 0, 4) {
    ii tmp = mp(x.fi + dx[i], x.se + dy[i]);
    if (tmp == y) return i;
  }
  return 0;
}

bool valid(ii u) {
  return u.fi >= 0 && u.fi < n && u.se >= 0 && u.se < m;
}

void dijktra() {
  memset(d, 0x3f, sizeof d);
  priority_queue<iii, vector<iii>, greater<iii>> pq;
  pq.push(mp(0, st));
  d[st.fi][st.se] = 0;

  while (sz(pq)) {
    ii u = pq.top().se;
    int w = pq.top().fi;
    pq.pop();

    int idx = get(ch[u.fi][u.se]);
    if (ch[u.fi][u.se] == 'o') idx = -1;
    if (ch[u.fi][u.se] == 'x') return;

    forw(i, 0, 4) {
      ii v = mp(u.fi + dx[i], u.se + dy[i]);

      // if (u.fi == 0 && u.se == 2) cerr << v.fi << ' ' << v.se << endl;
      if (valid(v) && d[v.fi][v.se] > d[u.fi][u.se] + (i != idx)) {
        d[v.fi][v.se] = d[u.fi][u.se] + (i != idx);
        tr[v.fi][v.se] = mp(u.fi, u.se);
        pq.push(mp(d[v.fi][v.se], mp(v.fi, v.se)));
      }
    }
  }
}

void trace() {
  // des = tr[des.fi][des.se];
  for (; tr[des.fi][des.se].fi != -1; ) {
    // cerr << des.fi << ' ' << des.se << endl;
    int idx = getindx(mp(des.fi, des.se), tr[des.fi][des.se]);
    des = tr[des.fi][des.se];

    if (ch[des.fi][des.se] == 'o') return;
    if (!idx) ch[des.fi][des.se] = 'v';
    else if (idx == 1) ch[des.fi][des.se] = '>';
    else if (idx == 2) ch[des.fi][des.se] = '^';
    else ch[des.fi][des.se] = '<';
  }
}

int main() {
  fastIO;

  memset(tr, -1, sizeof tr);
  cin >> n >> m;
  forw(i, 0, n) forw(j, 0, m) {
    cin >> ch[i][j];
    if (ch[i][j] == 'o') st = mp(i, j);
    if (ch[i][j] == 'x') des = mp(i, j);
  }

  dijktra();
  cout << d[des.fi][des.se] - 1 << endl;  

  trace();
  forw(i, 0, n) {
    forw(j, 0, m) cout << ch[i][j];
    cout << '\n';
  }
}

Compilation message

Main.cpp: In function 'void dijktra()':
Main.cpp:72:9: warning: unused variable 'w' [-Wunused-variable]
   72 |     int w = pq.top().fi;
      |         ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 79076 KB Output is correct
2 Correct 39 ms 79156 KB Output is correct
3 Correct 36 ms 79096 KB Output is correct
4 Correct 42 ms 79168 KB Output is correct
5 Correct 38 ms 79124 KB Output is correct

Subtask #2
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 79076 KB Output is correct
2 Correct 39 ms 79156 KB Output is correct
3 Correct 36 ms 79096 KB Output is correct
4 Correct 42 ms 79168 KB Output is correct
5 Correct 38 ms 79124 KB Output is correct
6 Correct 115 ms 80932 KB Output is correct
7 Correct 136 ms 84124 KB Output is correct
8 Correct 282 ms 82692 KB Output is correct
9 Correct 548 ms 94452 KB Output is correct
10 Correct 768 ms 86076 KB Output is correct
11 Correct 1304 ms 107756 KB Output is correct