Submission #88699

#TimeUsernameProblemLanguageResultExecution timeMemory
88699popovicirobertTracks in the Snow (BOI13_tracks)C++14
2.19 / 100
1288 ms309456 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long // 217 // 44 using namespace std; const int MAXN = 4000; char mat[MAXN + 1][MAXN + 1]; int sef[MAXN * MAXN + 1]; int myfind(int x) { if(sef[x] == 0) return x; return sef[x] = myfind(sef[x]); } inline void myunion(int x, int y) { x = myfind(x), y = myfind(y); if(x != y) { sef[x] = y; } } bool vis[MAXN * MAXN + 1]; char dl[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1}; int n, m; inline bool in(int l, int c) { return 1 <= l && l <= n && 1 <= c && c <= m; } inline int get(int l, int c) { return (l - 1) * m + c; } inline int solve(char ch) { int i, j; memset(sef, 0, sizeof(sef)); for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { if(mat[i][j] == ch) { for(int p = 0; p < 4; p++) { int l = i + dl[p], c = j + dc[p]; if(in(l, c)) { myunion(get(l, c), get(i, j)); } } } } } memset(vis, 0, sizeof(vis)); int ans = 1; for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { if(mat[i][j] == ch) { if(!vis[myfind(get(i, j))]) { vis[myfind(get(i, j))] = 1; ans++; } } } } return ans; } int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, j; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> m; int cntF = 0, cntR = 0; for(i = 1; i <= n; i++) { cin >> mat[i] + 1; for(j = 1; j <= m; j++) { if(mat[i][j] == 'R') { cntR++; } if(mat[i][j] == 'F') { cntF++; } } } if(cntF + cntR == 0) { cout << 0; return 0; } if(cntF == 0 || cntR == 0) { cout << 1; return 0; } int ans = solve('R'); ans = min(ans, solve('F')); cout << ans; //cin.close(); //cout.close(); return 0; }

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:79:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin >> mat[i] + 1;
                ~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...