Submission #1107976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107976		0pt1mus23	Tracks in the Snow (BOI13_tracks)	C++14	14.27 / 100	2082 ms	929608 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 = 4005, inf = INT_MAX, LL = 30;
 

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

int comp[sze][sze];
map<pair<int,int>,int> var;
vector<int> graph[sze*sze];
int used[sze*sze];
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 c=1,a,b;
    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]= (c++);
                }
                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];
                        }
                        else{
                            if(arr[x][y]!='.' && comp[x][y]){
                                a = comp[x][y];
                                b = comp[i][j];
                                if(!var[make_pair(min(a,b),max(a,b))]){
                                    var[make_pair(min(a,b),max(a,b))]=1;
                                    graph[a].pb(b);
                                    graph[b].pb(a);
                                }
                            }
                        }
                    }
                }
            }
        }
    }



    int ans=1;
    queue< pair<int,int>> q;
    q.push({1,1});
    while(!q.empty()){
        pair<int,int> node =q.front();
        q.pop();
        if(!used[node.first]){
            ans=max(ans,node.second);
            used[node.first]=1;
            for(auto v:graph[node.first]){
                if(!used[v]){
                    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: 3.3333333333333335 / 30
• Subtask 2: 10.9375 / 70