Submission #1107983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107983		0pt1mus23	Tracks in the Snow (BOI13_tracks)	C++11	2.19 / 100	1936 ms	811664 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]=0;
            cin>>arr[i][j];
        }
    }
 
    int x,y;
    int ct=1,a,b,u,v;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]!='.'){
                if(!comp[i][j]){
                    comp[i][j]= (ct++);
                }
                for(int k=0;k<4;k++){
                    x= i + dx[k];
                    y = j + dy[k];
                    if( x>=0 && y>=0 && x<n && y<m){
                        if(arr[i][j] == arr[x][y]){
                            comp[x][y]=comp[i][j];
                        }
                    }
                }
            }
        }
    }
 
    vector<int> graph[ct+10];
    for( int i=0;i<=ct;i++){
        graph[i]=vector<int>();
    }
    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++){
                    a = i + dx[x];
                    b = j + dy[x];
                    if(a>=0 && a<n && b>=0 && b<m && comp[a][b] !=-1 && comp[a][b]!=comp[i][j]){

                        u = min(comp[i][j],comp[a][b]);
                        v =max(comp[i][j],comp[a][b]);
                        // cout<<u<<" "<<v<<endl;
                        graph[u].pb(v);
                        graph[v].pb(u);
                    }
                }
 
            }
        }
    }
    int ans=0;
    queue<pair<int,int>> q;
    vector<int> used(ct,0);
    q.push({1,1});
    used[1]=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);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        rush();
    }
 
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70