Submission #511190

#TimeUsernameProblemLanguageResultExecution timeMemory
511190DragosC1Tracks in the Snow (BOI13_tracks)C++17
97.81 / 100
1681 ms1048580 KiB
#include <iostream> #include <queue> #include <vector> #include <set> using namespace std; vector<vector<int>> a; char mat[4001][4001]; int comp[4001][4001]; bool viz[16000001]; queue<pair<int, int>> Q; #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m; int l; int Max; const int di[] = {-1, 0, 1, 0}; const int dj[] = {0, 1, 0, -1}; bool inside(int i, int j) { if (i >= 1 && i <= n && j >= 1 && j <= m) return 1; return 0; } void dfs1(int i, int j) { int k, inou, jnou; comp[i][j] = l; for (k = 0; k < 4; k++) { inou = i + di[k], jnou = j + dj[k]; if (inside(inou, jnou) && !comp[inou][jnou] && mat[inou][jnou] == mat[i][j]) dfs1(inou, jnou); } } void dfs2(int i, int j) { int k, inou, jnou; viz[(i - 1) * m + j] = 1; for (k = 0; k < 4; k++) { inou = i + di[k], jnou = j + dj[k]; if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] == mat[i][j]) dfs2(inou, jnou); else if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] != '.') { a[comp[i][j]].emplace_back(comp[inou][jnou]); a[comp[inou][jnou]].emplace_back(comp[i][j]); } } } void bfs(int x) { int i; pair<int, int> p; Q.push({x, 1}); viz[x] = 1; while (!Q.empty()) { p = Q.front(); Q.pop(); if (p.second > Max) Max = p.second; for (int x : a[p.first]) { if (!viz[x]) { viz[x] = 1; Q.push({x, p.second + 1}); } } } } int main() { fast int i, j; cin >> n >> m; for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) cin >> mat[i][j]; for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) if (!comp[i][j] && mat[i][j] != '.') { l++; dfs1(i, j); } a.resize(l + 1); for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) if (!viz[(i - 1) * m + j] && mat[i][j] != '.') dfs2(i, j); for (i = 1; i <= l; i++) viz[i] = 0; bfs(1); cout << Max; return 0; }

Compilation message (stderr)

tracks.cpp: In function 'void bfs(int)':
tracks.cpp:53:9: warning: unused variable 'i' [-Wunused-variable]
   53 |     int i;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...