Submission #363668

#	Time	Username	Problem	Language	Result	Execution time	Memory
363668		dolphingarlic	Connect (CEOI06_connect)	C++14	65 / 100	98 ms	65540 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

connect

#include <bits/stdc++.h> using namespace std; struct State { State *prv; short cost, type; State(short _cost = 1000) : prv(nullptr), cost(_cost), type(-1) {} State(State *_prv, short _type) : prv(_prv), type(_type), cost(_prv->cost) { if (type < 4) cost++; else if (type < 10) cost += 2; } State(State *_prv1, short _type1, State *_prv2, short _type2) { if (_prv1->cost < _prv2->cost) prv = _prv1, type = _type1; else prv = _prv2, type = _type2; cost = prv->cost; if (type < 4) cost++; else if (type < 10) cost += 2; } }; string grid[25]; State *dp[12][40][1 << 13]; int main() { cin.tie(0)->sync_with_stdio(0); int r, c; cin >> r >> c; getline(cin, grid[0]); // Buffer stuff >:( for (int i = 0; i < r; i++) getline(cin, grid[i]); int n = r >> 1, m = c >> 1; for (int i = 0; i < n; i++) for (int j = 0; j <= m; j++) for (int mask = 0; mask < (1 << n + 1); mask++) dp[i][j][mask] = new State(); dp[n - 1][0][0] = new State(0); for (int j = 1; j <= m; j++) { for (int i = 0; i < n; i++) { for (int mask = 0; mask < (1 << n + 1); mask++) { int r = mask & (1 << i), d = mask & (1 << i + 1); // You can't connect over a blocked corridor if (r && grid[2 * i + 1][2 * j] == '|') continue; if (d && grid[2 * i + 2][2 * j - 1] == '-') continue; // An 'X' can't have more than 1 paths going out from it if (r && d && grid[2 * i + 1][2 * j - 1] == 'X') continue; // Casework for the DP if (!i) { int prv_base = (mask >> 2) << 1; if (grid[2 * i + 1][2 * j - 1] == 'X') { if (r || d) { if (r) dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base], 1); if (d) dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base], 2); } else dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base + 1], 3); } else { if (r && d) dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base], 7); else if (r || d) { if (r) dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base + 1], 8); if (d) dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base + 1], 9); } else dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base], 10); } } else { int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1)); if (grid[2 * i + 1][2 * j - 1] == 'X') { if (r || d) { if (r) dp[i][j][mask] = new State(dp[i - 1][j][prv_base], 1); if (d) dp[i][j][mask] = new State(dp[i - 1][j][prv_base], 2); } else dp[i][j][mask] = new State( dp[i - 1][j][prv_base + (1 << i)], 0, dp[i - 1][j][prv_base + (1 << i + 1)], 3); } else { if (r && d) dp[i][j][mask] = new State(dp[i - 1][j][prv_base], 7); else if (r || d) { if (r) dp[i][j][mask] = new State( dp[i - 1][j][prv_base + (1 << i)], 4, dp[i - 1][j][prv_base + (1 << i + 1)], 8); if (d) dp[i][j][mask] = new State( dp[i - 1][j][prv_base + (1 << i)], 5, dp[i - 1][j][prv_base + (1 << i + 1)], 9); } else dp[i][j][mask] = new State( dp[i - 1][j][prv_base + (1 << i) + (1 << i + 1)], 6, dp[i - 1][j][prv_base], 10); } } } } } cout << dp[n - 1][m][0]->cost << '\n'; State *curr = dp[n - 1][m][0]; for (int j = m - 1; ~j; j--) for (int i = n - 1; ~i; i--) { if (curr->type == 0) grid[2 * i][2 * j + 1] = '.'; else if (curr->type == 1) grid[2 * i + 1][2 * j + 2] = '.'; else if (curr->type == 2) grid[2 * i + 2][2 * j + 1] = '.'; else if (curr->type == 3) grid[2 * i + 1][2 * j] = '.'; else if (curr->type == 4) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j + 2] = '.'; else if (curr->type == 5) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 2][2 * j + 1] = '.'; else if (curr->type == 6) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.'; else if (curr->type == 7) grid[2 * i + 1][2 * j + 2] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 2][2 * j + 1] = '.'; else if (curr->type == 8) grid[2 * i + 1][2 * j + 2] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.'; else if (curr->type == 9) grid[2 * i + 2][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.'; curr = curr->prv; } for (int i = 0; i < r; i++) cout << grid[i] << '\n'; return 0; }

Compilation message (stderr)

connect.cpp: In constructor 'State::State(State*, short int)':
connect.cpp:6:17: warning: 'State::type' will be initialized after [-Wreorder]
    6 |     short cost, type;
      |                 ^~~~
connect.cpp:6:11: warning:   'short int State::cost' [-Wreorder]
    6 |     short cost, type;
      |           ^~~~
connect.cpp:9:5: warning:   when initialized here [-Wreorder]
    9 |     State(State *_prv, short _type) : prv(_prv), type(_type), cost(_prv->cost) {
      |     ^~~~~
connect.cpp: In function 'int main()':
connect.cpp:35:47: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   35 |             for (int mask = 0; mask < (1 << n + 1); mask++)
      |                                             ~~^~~
connect.cpp:40:47: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   40 |             for (int mask = 0; mask < (1 << n + 1); mask++) {
      |                                             ~~^~~
connect.cpp:41:61: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   41 |                 int r = mask & (1 << i), d = mask & (1 << i + 1);
      |                                                           ~~^~~
connect.cpp:63:53: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   63 |                     int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
      |                                                   ~~^~~
connect.cpp:63:84: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   63 |                     int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
      |                                                                                  ~~^~~
connect.cpp:63:74: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   63 |                     int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
      |                                                                 ~~~~~~~~~^~~~~~~~~~~~~~
connect.cpp:70:65: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   70 |                                 dp[i - 1][j][prv_base + (1 << i + 1)], 3);
      |                                                               ~~^~~
connect.cpp:76:69: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   76 |                                     dp[i - 1][j][prv_base + (1 << i + 1)], 8);
      |                                                                   ~~^~~
connect.cpp:79:69: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |                                     dp[i - 1][j][prv_base + (1 << i + 1)], 9);
      |                                                                   ~~^~~
connect.cpp:81:76: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   81 |                                 dp[i - 1][j][prv_base + (1 << i) + (1 << i + 1)], 6,
      |                                                                          ~~^~~

Subtask 165 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...