Submission #1065817

#TimeUsernameProblemLanguageResultExecution timeMemory
1065817ortsacTracks in the Snow (BOI13_tracks)C++17
2.19 / 100
1286 ms204412 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define fr first #define se second const int MAXT = 4e3 + 10; char mat[MAXT][MAXT]; pii dad[MAXT][MAXT]; int tam[MAXT][MAXT]; int cR = 0, cF = 0; int n, m; int x[] = {-1, 0, 0, 1}; int y[] = {0, -1, 1, 0}; bool valid(int i, int j) { return ((1 <= i) && (n >= i) && (j >= 1) && (j <= m)); } pii find(pii x) { if (dad[x.fr][x.se] == x) return x; return dad[x.fr][x.se] = find(dad[x.fr][x.se]); } void print(pii a) { cout << a.fr << " " << a.se << "\n"; } void join(pii a, pii b) { a = find(a), b = find(b); if (a == b) return; if (tam[a.fr][a.se] > tam[b.fr][b.se]) swap(a, b); tam[b.fr][b.se] += tam[a.fr][a.se]; dad[a.fr][a.se] = b; } int32_t main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> mat[i][j]; if (mat[i][j] != '.') { tam[i][j] = 1; dad[i][j] = {i, j}; } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (mat[i][j] == '.') continue; for (int k = 0; k < 4; k++) { int a = i + x[k], b = j + y[k]; if ((!valid(a, b)) || (mat[i][j] != mat[a][b])) continue; join({i, j}, {a, b}); } } } // calc componentes for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (mat[i][j] == '.') continue; if (dad[i][j] != make_pair(i, j)) continue; if (mat[i][j] == 'R') cR++; else cF++; } } // resposta if (min(cR, cF) == 0) cout << "1\n"; else cout << "2\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...