Submission #1193820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193820		empaktus	Tracks in the Snow (BOI13_tracks)	C++20	59.38 / 100	1768 ms	820328 KiB

tracks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;

void cas(){
	int n,m;
	cin>>n>>m;
	vector<string>board(n);
	for(int i=0;i<n;i++){
		cin>>board[i];
	}
	vector<vector<int>>col(n,vector<int>(m,-1));

	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(col[i][j]!=-1){
				continue;
			}
			if(board[i][j]=='.'){
				continue;
			}
			col[i][j]=i*n+j;
			queue<pair<int,int>>q;
			q.push({i,j});
			while(!q.empty()){
				pair<int,int> v=q.front();
				q.pop();
				vector<pair<int,int>>delta={{1,0},{0,1},{-1,0},{0,-1}};
				
				//for(int x:adj[v.first][v.second]){
				for(auto [dx,dy]:delta){
					pair<int,int>x={v.first+dx,v.second+dy};
					if(x.first>=0&&x.first<n&&x.second>=0&&x.second<m){
						if(board[x.first][x.second]==board[v.first][v.second]){
							if(col[x.first][x.second]==-1){
								q.push(x);
								col[x.first][x.second]=col[v.first][v.second];
							}
						}
					}
				}
			}
		}
	}
	
	/*for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cout<<col[i][j]<<" ";
		}
		cout<<"\n";
	}*/
	vector<vector<int>>adj(n*m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			vector<pair<int,int>>delta={{1,0},{0,1},{-1,0},{0,-1}};
			for(auto [dx,dy]:delta){
				pair<int,int>x={i+dx,j+dy};
				if(x.first>=0&&x.first<n&&x.second>=0&&x.second<m){
					if(col[i][j]!=-1&&col[x.first][x.second]!=-1){
						adj[col[i][j]].push_back(col[x.first][x.second]);
					}
				}
			}
		}
	}
	
	vector<int>dist(n*m,-1);
	dist[0]=0;
	queue<int>q;
	q.push(0);
	while(!q.empty()){
		int v=q.front();
		q.pop();
		for(int x:adj[v]){
			if(dist[x]==-1){
				q.push(x);
				dist[x]=dist[v]+1;
			}
		}
	}
	int ans=0;
	for(int i=0;i<n*m;i++){
		ans=max(ans,dist[i]);
	}
	cout<<ans+1<<"\n";
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cas();
	
}

• Subtask 1: 20 / 30
• Subtask 2: 39.375 / 70