Submission #1301819

#TimeUsernameProblemLanguageResultExecution timeMemory
1301819JelaByteEngineerTracks in the Snow (BOI13_tracks)C++20
0 / 100
2132 ms1114112 KiB
#include <bits/stdc++.h> using namespace std; vector <vector <int>> g1, g2; void dfs (int node, vector <bool> &vis) { vis[node]=true; for (auto i: g1[node]) { if (!vis[i]) dfs(i, vis); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin>>n>>m; vector <vector <char>> mat(n, vector <char> (m)); map <pair<int, int>, int> mapa1, mapa2; int cntu=0, cntf=0; for (int i=0; i<n; i++) { string s; cin>>s; for (int j=0; j<m; j++) { mat[i][j]=s[j]; if (s[j]!='.') { mapa1[{i, j}]=cntu; cntu++; } if (s[j]=='F') { mapa2[{i, j}]=cntf; cntf++; } } } g1.resize(cntu, vector <int> (cntu)); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (mat[i][j]!='.') { if (i-1>=0 && mat[i-1][j]!='.') { g1[mapa1[{i, j}]].push_back(mapa1[{i-1, j}]); } if (i+1<n && mat[i+1][j]!='.') { g1[mapa1[{i, j}]].push_back(mapa1[{i+1, j}]); } if (j-1>=0 && mat[i][j-1]!='.') { g1[mapa1[{i, j}]].push_back(mapa1[{i, j-1}]); } if (j+1<m && mat[i][j+1]!='.') { g1[mapa1[{i, j}]].push_back(mapa1[{i, j+1}]); } } } } g2.resize(cntf, vector <int> (cntf)); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (mat[i][j]!='.') { if (i-1>=0 && mat[i-1][j]!='.') { g2[mapa2[{i, j}]].push_back(mapa2[{i-1, j}]); } if (i+1<n && mat[i+1][j]!='.') { g2[mapa2[{i, j}]].push_back(mapa2[{i+1, j}]); } if (j-1>=0 && mat[i][j-1]!='.') { g2[mapa2[{i, j}]].push_back(mapa2[{i, j-1}]); } if (j+1<m && mat[i][j+1]!='.') { g2[mapa2[{i, j}]].push_back(mapa2[{i, j+1}]); } } } } vector <bool> vis1(cntu, false); vector <bool> vis2(cntf, false); int ans=0; for (int i=0; i<cntu; i++) { if (!vis1[i]) { ans++; dfs(i, vis1); } } for (int i=0; i<cntf; i++) { if (!vis2[i]) { ans++; dfs(i, vis2); } } cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...