oj.uz

Submission #221571

# Submission time Handle Problem Language Result Execution time Memory
221571 2020-04-10T13:47:57 Z Haunted_Cpp Zoo (COCI19_zoo) C++17
45 / 110
 2000 ms 10920 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <string>
#include <cstring>
#include <bitset>
#include <random>
#include <chrono>
#include <iomanip>
 
/*
#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
*/
 
#define FOR(i, a, b) for(int i = a; i < (int) b; i++)
#define F0R(i, a) FOR (i, 0, a)
#define ROF(i, a, b) for(int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
 
#define rsz resize
#define eb emplace_back
#define pb push_back
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define f first
#define s second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;
 
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};
 
const int N = 1e3 + 5;

int ordem_visita = 1;
int vis [N][N];
char g [N][N];
 
int r, c;
 
void dfs (int linha, int coluna, char t) {
  if (linha < 0 || coluna < 0 || linha >= r || coluna >= c) return;
  if (g[linha][coluna] == '*') return;
  if (vis[linha][coluna] == ordem_visita) return;
  if (g[linha][coluna] == 'B' || g[linha][coluna] == 'T') if (g[linha][coluna] != t) return;
  vis[linha][coluna] = ordem_visita;
  g[linha][coluna] = '#';
  F0R (i, 4) dfs (linha + dr[i], coluna + dc[i], t);
}

bool can_reach (int linha, int coluna, char t) {
  if (linha < 0 || coluna < 0 || linha >= r || coluna >= c) return false;
  if (linha == 0 && coluna == 0) return true;
  if (g[linha][coluna] == '*') return false;
  if (vis[linha][coluna] == ordem_visita) return false;
  if (g[linha][coluna] == 'B' || g[linha][coluna] == 'T') if (g[linha][coluna] != t) return false;
  vis[linha][coluna] = ordem_visita;
  bool ans = false;
  F0R (i, 4) ans |= can_reach (linha + dr[i], coluna + dc[i], t);
  return ans;
}
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> r >> c;
  F0R (i, r) F0R (j, c) cin >> g[i][j];
  int res = 0;
  while (1) {
    F0R (i, r) F0R (j, c) {
      if (g[i][j] == '*') continue;
      if (g[i][j] == '#') continue;
      if (can_reach (i, j, g[i][j]) == false) continue;
      ++ordem_visita;
      ++res;
      dfs (i, j, g[i][j]);
      ++ordem_visita;
    }
    F0R (i, r) F0R (j, c) if (g[i][j] == 'B' || g[i][j] == 'T') goto fim;
    break;
    fim:;
  }
  cout << res << '\n';
  return 0;
}

Subtask #1
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 6 ms 896 KB Output is correct
8 Correct 16 ms 896 KB Output is correct
9 Correct 16 ms 896 KB Output is correct
10 Correct 20 ms 1024 KB Output is correct
11 Correct 23 ms 896 KB Output is correct
12 Correct 23 ms 1024 KB Output is correct
13 Correct 16 ms 768 KB Output is correct
14 Correct 16 ms 896 KB Output is correct
15 Correct 17 ms 768 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 6 ms 896 KB Output is correct
8 Correct 16 ms 896 KB Output is correct
9 Correct 16 ms 896 KB Output is correct
10 Correct 20 ms 1024 KB Output is correct
11 Correct 23 ms 896 KB Output is correct
12 Correct 23 ms 1024 KB Output is correct
13 Correct 16 ms 768 KB Output is correct
14 Correct 16 ms 896 KB Output is correct
15 Correct 17 ms 768 KB Output is correct
16 Correct 49 ms 6776 KB Output is correct
17 Correct 51 ms 6904 KB Output is correct
18 Correct 50 ms 6400 KB Output is correct
19 Correct 64 ms 7292 KB Output is correct
20 Correct 49 ms 6648 KB Output is correct
21 Execution timed out 2079 ms 10920 KB Time limit exceeded
22 Halted 0 ms 0 KB -