Submission #366295

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
366295	2021-02-13T19:49:27 Z	model_code	Patkice II (COCI21_patkice2)	C++17	110 / 110	1290 ms	78376 KB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair
#define pb push_back

struct State {
  int dist;
  int a, b, c, d;

  State(){}
  State(int _dist, int _a, int _b, int _c, int _d) {
    dist = _dist;
    a = _a;
    b = _b;
    c = _c;
    d = _d;
  }

  friend bool operator < (const State &a, const State &b) {
    return a.dist > b.dist;
  }
};

const int MAXN = 2005;

const int smjerx[] = {0, 0, -1, 1};
const int smjery[] = {1, -1, 0, 0};
const string znak = "><^v";

int n, m;
char s[MAXN][MAXN];

priority_queue <State> q;

bool bio[MAXN][MAXN];
pii odkud[MAXN][MAXN];

int dijkstra() {
  while (!q.empty()) {
    while (!q.empty() && bio[q.top().a][q.top().b]) q.pop();
    State t = q.top();
    q.pop();
    bio[t.a][t.b] = 1;
    odkud[t.a][t.b] = {t.c, t.d};
    if (s[t.a][t.b] == 'x') {
      return t.dist;
    }

    REP(i, 4) {
      int nx = t.a + smjerx[i];
      int ny = t.b + smjery[i];
      if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
      if (bio[nx][ny]) continue;
      q.push(State(t.dist + (s[t.a][t.b] != znak[i]), nx, ny, t.a, t.b));
    }
  }
  assert(0);
  return -1;
}

void recon() {
  int x, y;
  REP(i, n) REP(j, m) if (s[i][j] == 'x') {
    x = i;
    y = j;
  }
  while (s[x][y] != 'o') {
    int nx = odkud[x][y].fi;
    int ny = odkud[x][y].sec;
    REP(i, 4) {
      if (nx + smjerx[i] == x && ny + smjery[i] == y) {
        if (s[nx][ny] != 'o') s[nx][ny] = znak[i];
        break;
      }
    }
    x = nx;
    y = ny;
  }
  REP(i, n) {
    REP(j, m) {
      printf("%c",s[i][j]);
    }
    puts("");
  }
}

int main() {
  scanf("%d %d",&n,&m);
  REP(i, n) scanf("%s",s[i]);

  REP(i, n) {
    REP(j, m) {
      if (s[i][j] == 'o') q.push(State(0, i, j, -1, -1));
    }
  }

  printf("%d\n",dijkstra() - 1);
  recon();
  return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |   scanf("%d %d",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~~
Main.cpp:104:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |   REP(i, n) scanf("%s",s[i]);
      |             ~~~~~^~~~~~~~~~~
Main.cpp: In function 'void recon()':
Main.cpp:82:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |   while (s[x][y] != 'o') {
      |          ~~~~~~^
Main.cpp:82:16: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	97 ms	7316 KB	Output is correct
7	Correct	138 ms	17056 KB	Output is correct
8	Correct	319 ms	17228 KB	Output is correct
9	Correct	535 ms	43052 KB	Output is correct
10	Correct	894 ms	36776 KB	Output is correct
11	Correct	1290 ms	78376 KB	Output is correct