Submission #1108078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108078		0pt1mus23	Tracks in the Snow (BOI13_tracks)	C++11	71.98 / 100	2116 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 = 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};

struct DSU{
    vector<int> parent;
    vector<int> sz;
    DSU(int n){
        sz.resize(n+1,1);
        parent.resize(n+1);
        iota(all(parent),0);
    }
    int root(int node){
        if(parent[node]==node){
            return node;
        }
        return parent[node]=root(parent[node]);
    }
    void unite(int a,int b){
        int x = root(a);
        int y = root(b);
        if(x!=y){
            if(sz[x]<sz[y]){
                swap(x,y);
            }
            parent[y]=x;
            sz[x]+=sz[y];
        }
    }
};
void rush(){
    int n,m;
    cin>>n>>m;  
    DSU dsu(4005*4005);
    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;
    int u,v,a,b;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]!='.'){
                if(comp[i][j]==-1){
                    comp[i][j]=(ct++);
                }
                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 && arr[a][b]==arr[i][j]){
                        if(comp[a][b]!=-1){
                            dsu.unite(comp[a][b],comp[i][j]);
                        }
                        comp[a][b]=dsu.root(comp[i][j]);
                    }
                }
            }
        }
    }
    map<int,vector<pair<int,int>>> cp;
    ct=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(comp[i][j]!=-1){
                cp[dsu.root(comp[i][j])].pb({i,j});
            }
        }
    }
    for(auto &v:cp){
        for(auto pp:v.second){
            // cout<<pp.first<<" "<<pp.second<<endl;
            comp[pp.first][pp.second]=ct;
        }
        ct++;
    }
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         cout<<comp[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    set<int> graph[ct+11];
    for(int i=0;i<=ct;i++){
        graph[i].clear();
    }
    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]);
                        graph[u].ins(v);
                        graph[v].ins(u);
                    }
                }
 
            }
        }
    }
    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;
}

• Subtask 1: 21.666666666666668 / 30
• Subtask 2: 50.3125 / 70