Submission #531654

#	Time	Username	Problem	Language	Result	Execution time	Memory
531654		Tam_theguide	Tracks in the Snow (BOI13_tracks)	C++14	19.38 / 100	1519 ms	1048580 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[4005][4005];
int belongto[4005][4005];
int component[160000005];
bool visited[4005][4005];
set<int>neighbors[4005];
bool gothere[160000005];
int source=0;
char core;
const int dx[4]={0, 0, 1, -1};
const int dy[4]={1, -1, 0, 0};
int temp=0;
deque<int>dq;
int ans=0;
int d[160000005];
bool check(int i, int j){
    if (1<=i && i<=n && 1<=j && j<=m) return true;
    else return false;
}
void floodfill(int i, int j, char cur){
    if (check(i, j)==false || visited[i][j] || a[i][j]!=cur || a[i][j]=='.') return;
    visited[i][j]=true;
    belongto[i][j]=temp;
    for (int t=0; t<4; t++){
        int u=i+dx[t];
        int v=j+dy[t];
        if (check(u, v) && belongto[u][v]!=0 && belongto[u][v]!=temp){
            neighbors[temp].insert(belongto[u][v]);
            neighbors[belongto[u][v]].insert(temp);
        }
        floodfill(u, v, cur);
    }
}
int main(){
    cin>>n>>m;
    for (int i=1;i <=n; i++){
        for (int j=1; j<=m; j++){
            cin>>a[i][j];
            if (i==1 && j==1){
                core=a[i][j];
            }

        }
    }
    for (int i=1;i <=n; i++){
        for (int j=1; j<=m; j++){
            if (visited[i][j]==false &&  a[i][j]!='.'){
                temp++;
                d[temp]=1e9;
                component[temp]=(a[i][j]!=core);
                floodfill(i, j, a[i][j]);
            }
        }
    }
  /*  for (int i=1; i<=temp; i++){
        cout<<i<<" "<<"component: "<<component[i]<<" neighbors: ";
        for (auto c:neighbors[i]){
            cout<<c<<" ";
        }
        cout<<endl;

    } */
    d[1]=1;

    dq.push_back(1);
    while (!dq.empty()){
        int x=dq.front();
        dq.pop_front();
        //cout<<"cac"<<endl;
        gothere[x]=true;
        for (auto c:neighbors[x]){
            if (gothere[c]) continue;
            if (component[c]!=component[x]){

                dq.push_back(c);
                d[c]=min(d[c], d[x]+1);
            }else{
                dq.push_front(c);
                d[c]=min(d[c], d[x]);
            }
        }
    }
    for (int i=1; i<=temp; i++){
        ans=max(ans, d[i]);
        //cout<<d[i]<<endl;
    }
    cout<<ans;

}

• Subtask 1: 15 / 30
• Subtask 2: 4.375 / 70