Submission #631287

#	Time	Username	Problem	Language	Result	Execution time	Memory
631287		czhang2718	Tracks in the Snow (BOI13_tracks)	C++17	93.44 / 100	2118 ms	1048576 KiB

tracks

#include "bits/stdc++.h"
using namespace std;

const int N=4000;
int n, m;
short dx[]={0, 0, 1, -1};
short dy[]={1, -1, 0, 0};
vector<int> adj[N*N];
int vis[N*N];
short grid[N][N];
int cmp[N][N];

void dfs(int u, int c){
    cmp[u/m][u%m]=c;
    int i=u/m;
    int j=u%m;
    for(int k=0; k<4; k++){
        int x=i+dx[k];
        int y=j+dy[k];
        if(x<0 || x==n || y<0 || y==m || grid[x][y]!=grid[i][j] || cmp[x][y]) continue;
        dfs(m*x+y, c);
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            char c; cin >> c;
            grid[i][j]=(c=='F'?2:c=='R'?1:0);
        }
    }

    int c=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(grid[i][j]==0 || cmp[i][j]) continue;
            dfs(m*i+j, ++c);
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(grid[i][j]==0) continue;
            for(int k=0; k<4; k++){
                int x=i+dx[k];
                int y=j+dy[k];
                if(x<0 || x==n || y<0 || y==m || grid[x][y]==grid[i][j] || grid[x][y]==0) continue;
                adj[cmp[i][j]].push_back(cmp[x][y]);
                adj[cmp[x][y]].push_back(cmp[i][j]);
            }
        }
    }

    // for(int i=0; i<n*m; i++){
    //     if(find(i)!=i) continue;
    //     sort(adj[i].begin(), adj[i].end());
    //     adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    //     // for(int k:adj[i]) cout << i << " " << k << "\n";
    // }

    queue<int> q;
    int r=cmp[0][0];
    q.push(r);
    for(; !q.empty(); q.pop()){
        int x=q.front();
        for(int k:adj[x]){
            if(!vis[k] && k!=r){
                vis[k]=vis[x]+1;
                q.push(k);
            }
        }
    }
    int mx=0;
    for(int i=1; i<=c; i++) mx=max(mx, vis[i]);
    cout << mx+1;
}
// when its been a long time since goodbye

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