Submission #553393

#	Time	Username	Problem	Language	Result	Execution time	Memory
553393		new_acc	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1564 ms	759656 KiB

tracks

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=4e3+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int n,m,res;
vector<pair<int,int> > curr[N*N];
bool vis[N][N];
char t[N][N];
bool inn(int a,int b){
	return (a>=1 and a<=n and b>=1 and b<=m and t[a][b]!='.');
}
void add(int a,int b,int odl){
	if(vis[a][b]) return;
	vis[a][b]=1;
	res=max(res,odl);
	if(inn(a+1,b) and !vis[a+1][b]){
		if(t[a][b]==t[a+1][b]) curr[odl].push_back({a+1,b});
		else curr[odl+1].push_back({a+1,b});
	}
	if(inn(a-1,b) and !vis[a-1][b]){
		if(t[a][b]==t[a-1][b]) curr[odl].push_back({a-1,b});
		else curr[odl+1].push_back({a-1,b});
	}
	if(inn(a,b+1) and !vis[a][b+1]){
		if(t[a][b]==t[a][b+1]) curr[odl].push_back({a,b+1});
		else curr[odl+1].push_back({a,b+1});
	}
	if(inn(a,b-1) and !vis[a][b-1]){
		if(t[a][b]==t[a][b-1]) curr[odl].push_back({a,b-1});
		else curr[odl+1].push_back({a,b-1});
	}
}
void solve(){
	cin>>n>>m;
	curr[1].push_back({1,1});
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) cin>>t[i][j];
	for(int i=1;i>0;i++){
		if(curr[i].size()==0) break;
		for(int j=0;j<curr[i].size();j++) add(curr[i][j].fi,curr[i][j].se,i);
	}
	cout<<res<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message (stderr)

tracks.cpp: In function 'void solve()':
tracks.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j=0;j<curr[i].size();j++) add(curr[i][j].fi,curr[i][j].se,i);
      |               ~^~~~~~~~~~~~~~~

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