Submission #910618

#TimeUsernameProblemLanguageResultExecution timeMemory
910618oblantisTracks in the Snow (BOI13_tracks)C++17
97.81 / 100
898 ms1048576 KiB
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define all(v) v.begin(), v.end() #define pb push_back #define ss second #define ff first #define vt vector using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int inf = 1e9; const int mod = 1e9+7; const int maxn = 4e3 + 1; char a[maxn][maxn]; bool was[maxn][maxn]; queue<pii> q; void go(int x, int y, char s){ if(a[x][y] != s)return; q.push({x, y}); was[x][y] = 1; if(!was[x - 1][y])go(x - 1, y, s); if(!was[x + 1][y])go(x + 1, y, s); if(!was[x][y - 1])go(x, y - 1, s); if(!was[x][y + 1])go(x, y + 1, s); } void solve() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ was[i][0] = was[i][m + 1] = 1; for(int j = 1; j <= m; j++){ cin >> a[i][j]; if(a[i][j] == '.')was[i][j] = 1; } } for(int i = 1; i <= m; i++)was[0][i] = was[n + 1][i] = 1; int ans = 0; char s = a[n][m]; go(n, m, s); while(!q.empty()){ pii nw = q.front(); q.pop(); int x = nw.ff, y = nw.ss; if(a[x][y] == s){ ans++, s = (s == 'R' ? 'F' : 'R'); } if(!was[x - 1][y])go(x - 1, y, s); if(!was[x + 1][y])go(x + 1, y, s); if(!was[x][y - 1])go(x, y - 1, s); if(!was[x][y + 1])go(x, y + 1, s); } cout << ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int times = 1; //cin >> times; for(int i = 1; i <= times; i++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...