Submission #631279

#TimeUsernameProblemLanguageResultExecution timeMemory
631279czhang2718Tracks in the Snow (BOI13_tracks)C++17
97.81 / 100
2124 ms722400 KiB
#include "bits/stdc++.h" using namespace std; const int N=4000; int n, m; string grid[N]; int par[N*N]; short rnk[N*N]; short dx[]={0, 0, 1, -1}; short dy[]={1, -1, 0, 0}; vector<int> adj[N*N]; int vis[N*N]; int find(int x){ return par[x]==x?x:par[x]=find(par[x]); } void join(int x, int y){ int a=find(x); int b=find(y); if(a==b) return; if(rnk[a]<rnk[b]) par[a]=b; else if(rnk[b]<rnk[a]) par[b]=a; else{ rnk[a]++; par[b]=a; } } 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++) par[i*m+j]=i*m+j; cin >> grid[i]; } for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(grid[i][j]=='.') 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]) continue; join(m*i+j, m*x+y); } } } for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(grid[i][j]=='.') 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]=='.') continue; int a=find(m*i+j), b=find(m*x+y); adj[a].push_back(b); adj[b].push_back(a); } } } // 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=find(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; // cout << "vis[" << k << "] = " << vis[k] << "\n"; q.push(k); } } } int mx=0; for(int i=0; i<n*m; i++) mx=max(mx, vis[i]); cout << mx+1; } // when its been a long time since goodbye
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...