oj.uz

Submission #221601

# Submission time Handle Problem Language Result Execution time Memory
221601 2020-04-10T14:09:52 Z Haunted_Cpp Zoo (COCI19_zoo) C++17
0 / 110
 13 ms 8832 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;

char g [N][N];
int comp [N][N];
int lvl [N];
vvi grafo (N);

int r, c, where = 0;

void dfs (int linha, int coluna, char t) {
  if (linha < 0 || coluna < 0 || linha >= r || coluna >= c) return;
  if (g[linha][coluna] != t) return;
  if (~comp[linha][coluna]) return;
  comp[linha][coluna] = where;
  F0R (i, 4) dfs (linha + dr[i], coluna + dc[i], t);
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> r >> c;
  F0R (i, r) F0R (j, c) cin >> g[i][j];
  memset (comp, -1, sizeof(comp));
  F0R (i, r) F0R (j, c) {
    if (g[i][j] == '*') continue;
    if (~comp[i][j]) continue;
    dfs (i, j, g[i][j]);
    ++where;
  }
  F0R (i, r) {
    F0R (j, c) {
      if (g[i][j] == '*') continue;
      F0R (x, 4) {
        if (i + dr[x] < 0 || j + dc[x] < 0 || i + dr[x] >= r || j + dc[x] >= c) continue;
        if (g[i + dr[x]][j + dc[x]] == '*' || g[i + dr[x]][j + dc[x]] == g[i][j]) continue;
        grafo[comp[i][j]].eb(comp[i + dr[x]][j + dc[x]]);
        grafo[comp[i + dr[x]][j + dc[x]]].eb(comp[i][j]);
      }
    }
  }
  memset (lvl, -1, sizeof(lvl));
  lvl[0] = 1;
  int res = 0;
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    res = max (res, lvl[node]);
    GO (to, grafo[node]) {
      if (lvl[to] == -1) {
        lvl[to] = lvl[node] + 1;
        q.push(to);
      }
    }
  }
  cout << res << '\n';
  return 0;
}

Subtask #1
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 7 ms 4280 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 7 ms 4352 KB Output is correct
5 Correct 7 ms 4480 KB Output is correct
6 Correct 7 ms 4480 KB Output is correct
7 Correct 7 ms 4480 KB Output is correct
8 Runtime error 13 ms 8832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 7 ms 4280 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 7 ms 4352 KB Output is correct
5 Correct 7 ms 4480 KB Output is correct
6 Correct 7 ms 4480 KB Output is correct
7 Correct 7 ms 4480 KB Output is correct
8 Runtime error 13 ms 8832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -