oj.uz

Submission #366296

# Submission time Handle Problem Language Result Execution time Memory
366296 2021-02-13T19:53:19 Z model_code Patkice II (COCI21_patkice2) C++17
55 / 110
 1250 ms 78176 KB 
#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() {
  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:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |   scanf("%d %d",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~~
Main.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   REP(i, n) scanf("%s",s[i]);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
15.0 / 30.0

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

Subtask #2
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 364 KB Partially correct
2 Partially correct 1 ms 364 KB Partially correct
3 Partially correct 1 ms 492 KB Partially correct
4 Partially correct 1 ms 364 KB Partially correct
5 Partially correct 1 ms 364 KB Partially correct
6 Partially correct 99 ms 7504 KB Partially correct
7 Partially correct 133 ms 16916 KB Partially correct
8 Partially correct 315 ms 17228 KB Partially correct
9 Partially correct 553 ms 43080 KB Partially correct
10 Partially correct 867 ms 36776 KB Partially correct
11 Partially correct 1250 ms 78176 KB Partially correct