Submission #1107881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107881		0pt1mus23	Tracks in the Snow (BOI13_tracks)	C++14	17.60 / 100	2114 ms	761844 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e5 +5, inf = INT_MAX, LL = 30;


int comp[4005][4005];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
void rush(){
    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()){
 
                    pair<int,int> 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<pair<int,int>> 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});
            }
        }
    }
    putr(ans);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1; 
    // cin>>tt;

    while(tt--){
        rush();
    }

    return 0;
}

• Subtask 1: 6.666666666666667 / 30
• Subtask 2: 10.9375 / 70