Submission #1108083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108083		0pt1mus23	Tracks in the Snow (BOI13_tracks)	C++14	75.94 / 100	2128 ms	1048576 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 = 4e3 +5, inf = INT_MAX, LL = 30;
 
int comp[sze][sze];
int used[sze][sze];
char arr[sze][sze];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
int ct=0;
int n,m;
void dfs(int i,int j,char ch){
    if(i<0 || i==n || j<0 || j==m || comp[i][j]!=-1 || arr[i][j]!=ch){
        return;
    }
    comp[i][j]=ct;
    for(int x =0;x<4;x++){
        dfs(i+dx[x],j+dy[x],ch);
    }
}
int a,b;
set<pair<int,int>> lst;
void dfs2(int i,int j){
    if(i<0 || i==n || j<0 || j==m || comp[i][j]==-1 || used[i][j]){
        return;
    }
    used[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]){
            lst.ins({min(comp[a][b],comp[i][j]),max(comp[a][b],comp[i][j])});
        }
        dfs2(a,b);
    }

}
void rush(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            comp[i][j]=-1;
            cin>>arr[i][j];
        }
    }
 
    int u,v;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]!='.' && comp[i][j]==-1){
                dfs(i,j,arr[i][j]);
                ct++;
            }
        }
    }
    vector<int> graph[ct+11];
    for(int i=0;i<=ct;i++){
        graph[i].clear();
    }
    dfs2(0,0);
    for(auto v:lst){
        graph[v.first].pb(v.second);
        graph[v.second].pb(v.first);
    }
    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);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        rush();
    }
 
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void rush()':
tracks.cpp:53:9: warning: unused variable 'u' [-Wunused-variable]
   53 |     int u,v;
      |         ^
tracks.cpp:53:11: warning: unused variable 'v' [-Wunused-variable]
   53 |     int u,v;
      |           ^

• Subtask 1: 30 / 30
• Subtask 2: 45.9375 / 70