제출 #1120761

#제출 시각아이디문제언어결과실행 시간메모리
1120761Captain_GeorgiaTracks in the Snow (BOI13_tracks)C++17
20.83 / 100
2173 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct DSU { vector<vector<array<int, 2>>> par; vector<vector<int>> sz; void init (int N, int M) { par.resize(N + 1); sz.resize(N + 1); for (int i = 0;i < N;i ++) { par[i].assign(M + 1, {-1, -1}); sz[i].assign(M + 1, 1); } } array<int, 2> get_par (array<int, 2> x) { if (par[x[0]][x[1]][0] == -1) return x; return par[x[0]][x[1]] = get_par(par[x[0]][x[1]]); } void add (array<int, 2> a, array<int, 2> b) { a = get_par(a); b = get_par(b); if (a == b) return; if (sz[a[0]][a[1]] < sz[b[0]][b[1]]) swap (a, b); sz[a[0]][a[1]] += sz[b[0]][b[1]]; par[b[0]][b[1]] = a; } }; int32_t main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M; vector<vector<int>> arr(N, vector<int>(M)); map<char, int> val; val['.'] = 1; val['F'] = 2; val['R'] = 3; for (int i = 0;i < N;i ++) { string S; cin >> S; for (int j = 0;j < M;j ++) { arr[i][j] = val[S[j]]; } } assert (arr[0][0] == arr[N - 1][M - 1] && arr[0][0] > 1); // for (int i = 0;i < N;i ++) { // for (int j = 0;j < M;j ++) { // cout << arr[i][j] << " "; // } cout << "\n"; // } cout << "\n"; DSU DS; DS.init (N, M); vector<int> X = {1, -1, 0, 0}; vector<int> Y = {0, 0, 1, -1}; vector<vector<int>> used(N, vector<int>(M, 0)), submx(N, vector<int>(M, 0)); map<array<int, 2>, set<array<int, 2>>> g; auto check = [&](int x, int y) -> bool { if (x < 0 || x >= N || y < 0 || y >= M || used[x][y] == 1 || arr[x][y] <= 1) return 0; return 1; }; for (int i = 0;i < N;i ++) { for (int j = 0;j < M;j ++) { for (int t = 0;t < 4;t ++) if (check (i + X[t], j + Y[t])) { if (arr[i][j] == arr[i + X[t]][j + Y[t]]) { DS.add ({i, j}, {i + X[t], j + Y[t]}); } } } } for (int i = 0;i < N;i ++) for (int j = 0;j < M;j ++) used[i][j] = 0; function<void(int, int)> dfss = [&](int sx, int sy) -> void { used[sx][sy] = 1; for (int i = 0;i < 4;i ++) if (check (X[i] + sx, Y[i] + sy) == true) { if (arr[sx][sy] == arr[X[i] + sx][Y[i] + sy]) { dfss (X[i] + sx, Y[i] + sy); } else { if (DS.get_par ({sx, sy}) != DS.get_par ({X[i] + sx, Y[i] + sy})) { if (g[DS.get_par ({sx, sy})].find(DS.get_par ({X[i] + sx, Y[i] + sy})) == g[DS.get_par ({sx, sy})].end() && g[DS.get_par ({X[i] + sx, Y[i] + sy})].find(DS.get_par ({sx, sy})) == g[DS.get_par ({sx + X[i], sy + Y[i]})].end()) { g[DS.get_par ({sx, sy})].insert(DS.get_par ({X[i] + sx, Y[i] + sy})); } } dfss (X[i] + sx, Y[i] + sy); } } }; dfss (0, 0); // queue<array<int, 4>> q; // q.push({0, 0, 0, 0}); // used[0][0] = 1; // while (q.size() > 0) { // auto [sx, sy, _x, _y] = q.front(); // q.pop(); // for (int i = 0;i < 4;i ++) if (check (X[i] + sx, Y[i] + sy) == true) { // if (arr[sx][sy] != arr[X[i] + sx][Y[i] + sy]) { // used[X[i] + sx][Y[i] + sy] = 1; // g[{_x, _y}].push_back({X[i] + sx, Y[i] + sy}); // q.push({X[i] + sx, Y[i] + sy, X[i] + sx, Y[i] + sy}); // // dfs_init (X[i] + sx, Y[i] + sy, X[i] + sx, Y[i] + sy); // } else { // } // } // } function<void(int, int)> dfs = [&](int sx, int sy) -> void { // cout << sx << " " << sy << " -- "; // for (auto [vx, vy] : g[{sx, sy}]) { // cout << vx << " " << vy << ", "; // } cout << "\n"; for (auto [vx, vy] : g[{sx, sy}]) { dfs (vx, vy); submx[sx][sy] = max(submx[sx][sy], submx[vx][vy]); } submx[sx][sy] ++; }; dfs (0, 0); cout << submx[0][0] << "\n"; } /* 5 6 RRRRRR .R...R FRRFRR FR.... .RRRRR */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...