Submission #1026217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026217		0pt1mus23	Zoo (COCI19_zoo)	C++14	110 / 110	277 ms	61780 KiB

zoo

#pragma GCC optimize("O3", "inline")
#define skillissue <bits/stdc++.h>
#define ultra_mal std

#include skillissue
using namespace ultra_mal;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());


#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 1e9 +7, sze = 1E3 +100, inf = LLONG_MAX, P = 1453;
// const int L = 30;

int comp[1100][1100];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
void cave(){
    int n,m;
    cin>>n>>m;

    vector<vector<char>> arr(n,vector<char>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            comp[i][j]=-1;
            cin>>arr[i][j];
        }
    }

    int ct = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]!='*' && comp[i][j]==-1){
                queue<pair<int,int>> q;
                q.push({i,j});
                comp[i][j]=ct;
                while(!q.empty()){

                    pii node = q.front();q.pop();
                    // cout<<node.first<<" "<<node.second<<endl;

                    for(int x=0;x<4;x++){
                        int a = node.first + dx[x];
                        int b =  node.second + dy[x];
                        if(a>=0 && a<n && b>=0 && b<m && comp[a][b]==-1 && arr[a][b]==arr[i][j]){
                            comp[a][b]=ct;
                            q.push({a,b});
                            // cout<<node.first<<" "<<node.second <<" _>"<<a<<" "<<b<<endl;
                        }
                    }

                }
                ct++;
            }

        }
    }

    set<pair<int,int>> edge;

    vector<int> graph[ct];
    for(int i =0;i<n;i++){
        for(int j=0;j<m;j++){
            if(comp[i][j]!=-1){

                for(int x= 0; x<4;x++){
                    int a = i + dx[x];
                    int b = j + dy[x];
                    if(a>=0 && a<n && b>=0 && b<m && comp[a][b] !=-1 && comp[a][b]!=comp[i][j]){
                        if(edge.find({comp[i][j],comp[a][b]})==edge.end()){
                            edge.insert({comp[i][j],comp[a][b]});
                            graph[comp[i][j]].pb(comp[a][b]);
                        }
                    }
                }

            }
        }
    }
    int ans=0;
    queue<pii> q;
    vector<int> used(ct,0);
    q.push({0,1});
    used[0]=1;
    while(!q.empty()){
        auto node = q.front();
        ans=max(ans,node.second);
        q.pop();
        for(auto v:graph[node.first]){
        if(!used[v]){
                used[v]=1;
                q.push({v,node.second+1});
            }
        }
    }
    drop(ans);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    
    while(tt--){
        cave();
    }

    return 0;
} 
 

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