Submission #1057686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057686		Requiem	Zoo (COCI19_zoo)	C++17	110 / 110	209 ms	57944 KiB

zoo

#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "zoo"
using namespace std;

/**Debugging Tool  **/
void __print(int x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}

template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}

void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

/*----------------------------------*/

/**  Vector nhieu chieu **/
template<int D, typename T>
struct Vec: public vector<Vec<D - 1, T>>{
     static_assert(D >= 1, "vector dimensions must be greater than 0");
     template<typename... Args>
     Vec(int n = 0, Args... args): vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)){
     }
};

template<typename T>
struct Vec<1, T>: public vector<T> {
    Vec(int n = 0, const T& val = T()): vector<T>(n, val) {};
};
/*--------------------------------*/

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 1009 + 9;
int n, m;
char str[MAXN][MAXN];
int idComponent[MAXN][MAXN], componentCount = 0;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

queue<ii> q;
vector<vector<int>> g;

map<ii, bool> mp;
bool valid(int x, int y){
    return x >= 1 and x <= n and y >= 1 and y <= m and str[x][y] != '*';
}

void bfs(int x, int y){
    idComponent[x][y] = ++componentCount;

    q.push(ii(x, y));

    while(!q.empty()){
          int x1 = q.front().fi;
          int y1 = q.front().se;
          q.pop();

          for(int d = 0; d < 4; d++){
              int nx = x1 + dx[d];
              int ny = y1 + dy[d];
              if (!idComponent[nx][ny] and valid(nx, ny) and str[nx][ny] == str[x1][y1]){
                  idComponent[nx][ny] = componentCount;
                  q.push(ii(nx, ny));
              }
          }
    }
}

ii best = ii(0, 0);

int dist[MAXN * MAXN];

void dfs(int u, int p, int d){
    queue<int> q;
    q.push(1);
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 1;

    int ans = 0;
    while(!q.empty()){
        int u = q.front();
        maximize(ans, dist[u]);
        q.pop();

        for(auto v: g[u]){
            if (minimize(dist[v], dist[u] + 1)){
                q.push(v);
            }
        }
    }
    cout << ans << endl;
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> str[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if (idComponent[i][j] == 0 and str[i][j] != '*'){
                bfs(i, j);
            }
        }
    }
    g.resize(componentCount + 1);
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= m; j++){
//            printf("%lld ", idComponent[i][j]);
//        }
//        printf("\n");
//    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if (i < n and str[i][j] != '*' and str[i + 1][j] != '*' and str[i + 1][j] != str[i][j]) {
//                printf("%lld %lld %lld\n", i, j, idComponent[i][j]);
                if (mp.find(ii(idComponent[i][j], idComponent[i + 1][j])) == mp.end()){
                    g[idComponent[i][j]].pb(idComponent[i + 1][j]);
                    g[idComponent[i + 1][j]].pb(idComponent[i][j]);
//                    printf("%lld %lld %lld %lld\n", i, j, i + 1, j);
//                    printf("%lld %lld\n", idComponent[i][j], idComponent[i + 1][j]);
                    mp[ii(idComponent[i][j], idComponent[i + 1][j])] = true;
                    mp[ii(idComponent[i + 1][j], idComponent[i][j])] = true;
                }
            }
            if (j < m and str[i][j] != '*' and str[i][j + 1] != '*' and str[i][j] != str[i][j + 1]) {
                if (mp.find(ii(idComponent[i][j], idComponent[i][j + 1])) == mp.end()){
//                    printf("%lld %lld %lld %lld\n", i, j, i, j + 1);
                    g[idComponent[i][j]].pb(idComponent[i][j + 1]);
                    g[idComponent[i][j + 1]].pb(idComponent[i][j]);
                    mp[ii(idComponent[i][j], idComponent[i][j + 1])] = true;
//                    printf("%lld %lld\n",idComponent[i][j], idComponent[i][j + 1]);

                    mp[ii(idComponent[i][j + 1], idComponent[i][j])] = true;
                }
            }
        }
    }
////
      dfs(idComponent[n][m], -1, 0);

}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE

--> Coi lai truoc khi nop
**/

Compilation message (stderr)

zoo.cpp:129:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  129 | main()
      | ^~~~
zoo.cpp: In function 'int main()':
zoo.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
zoo.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65