Submission #382041

#TimeUsernameProblemLanguageResultExecution timeMemory
382041AraragiPatkice II (COCI21_patkice2)C++17
0 / 110
1 ms492 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("00") typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; ll time() {return chrono::system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); const int inf = 1e9; const ll inf64 = 1e18; #define ft first #define fin(x) ifstream cin("x.in"); #define fout(x) ofstream cout("x.out"); #define sd second #define pb push_back #define sz(x) (int)x.size() char grid[2001][2001]; int dst[2001][2001]; bool was[2001][2001]; array<int, 2> mem[2001][2001]; int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; void solve() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) dst[i][j] = inf; int sx = 0, sy = 0, ex = 0, ey = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { cin >> grid[i][j]; if (grid[i][j] == 'o') { sx = i; sy = j; } else if (grid[i][j] == 'x') { ex = i; ey = j; } } queue< pair< pair<int, int>, int > > q; q.push({{0, sx}, sy}); was[sx][sy] = true; dst[sx][sy] = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) mem[i][j] = {-1, -1}; while (!q.empty()) { int cost = -q.front().ft.ft; int fx = q.front().ft.sd; int fy = q.front().sd; q.pop(); if (cost > dst[fx][fy]) continue; was[fx][fy] = true; for (int i = 0; i < 4; i++) { int cx = fx + steps[i][0]; int cy = fy + steps[i][1]; int pay = 1; if (fx == sx && fy == sy) pay = 0; if (steps[i][0] == 1 && grid[fx][fy] == 'v') pay = 0; if (steps[i][0] == -1 && grid[fx][fy] == '^') pay = 0; if (steps[i][1] == 1 && grid[fx][fy] == '>') pay = 0; if (steps[i][1] == -1 && grid[fx][fy] == '<') pay = 0; if (!(cx >= 0 && cx < n && cy >= 0 && cy < m && !was[cx][cy])) continue; if (cost + pay < dst[cx][cy]) { dst[cx][cy] = cost + pay; q.push({{-(cost + pay), cx}, cy}); mem[cx][cy] = {fx, fy}; } } } vector< array<int, 2> > path; int x = ex, y = ey; while (x != sx || y != sy) { path.pb({x, y}); auto nx = mem[x][y]; x = nx[0]; y = nx[1]; } //path.pb({sx, sy}); reverse(path.begin(), path.end()); //for (auto it : path) // cout << it[0] + 1 << " " << it[1] + 1 << " " << it[2] << '\n'; int lst = 0; for (int i = 0; i < sz(path) - 1; i++) { //cerr << path[i][0] + 1 << " " << path[i][1] + 1 << '\n'; //cerr << path[i + 1][0] + 1 << " " << path[i + 1][1] + 1 << '\n'; if (path[i + 1][0] - path[i][0] == 1) { grid[path[i][0]][path[i][1]] = 'v'; } else if (path[i][0] - path[i + 1][0] == 1) { grid[path[i][0]][path[i][1]] = '^'; } else if (path[i + 1][1] - path[i][1] == 1) { grid[path[i][0]][path[i][1]] = '>'; } else if (path[i][1] - path[i + 1][1] == 1) { grid[path[i][0]][path[i][1]] = '<'; } } cout << dst[ex][ey] << '\n'; for (int i = 0; i < n; i++, cout << '\n') for (int j = 0; j < m; j++) cout << grid[i][j]; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef _LOCAL_ system("color 2"); #endif // _LOCAL_ int t = 1; while (t--) solve(); }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:121:9: warning: unused variable 'lst' [-Wunused-variable]
  121 |     int lst = 0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...