Submission #489259

#	Time	Username	Problem	Language	Result	Execution time	Memory
489259		cotester	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	702 ms	113156 KiB

tracks

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <iterator>
#include <cstring>
#include <fstream>
#include <map>
#include <bitset>
#include <cassert>
#include <stdlib.h>
#include <climits>
#include <stack>
#include <complex> 

using namespace std;

#define fa(a,b)(memset(a,b,sizeof(a)));
#define fill2d(vec,val) for(auto &v:vec)fill(all(v),val)
#define mp(a,b)(make_pair(a,b))
#define pb(a) push_back(a)
#define FORE(i,a,b) for (int i = (a); i <= (b); ++i)
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (a); i >= (b); --i)
#define FR(i,a) FOR(i,0,a)

#define p (pi())
#define flag (cout<<"here"<<endl)
#define fast ios::sync_with_stdio(0);cin.tie(0)
#define sz(x) ((int)(x.size()))
#define f first
#define s second
#define all(x) begin(x), end(x)
#define in(r,R) (r>=0&&r<R)

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pii = pair<int, int>;
using pdd = pair<double, double>;

const int dx[8] = {1,0,-1,0,1,1,-1,-1}; //first 4 are normal
const int dy[8] = {0,1,0,-1,1,-1,1,-1};
const int MOD = 1000000007;
const ll NMOD = 1000000009;

const int AR_MAX = (1 << 7) - 1; //when using memeset
const int AR_MAX_VAL = 2139062143;
//^ Not recommended unless 
//  there's no other way do to what you need to do
const double PI  =3.141592653589793238463;
const double EPS = 10e-9;

void _forAllUnusedConsts() { 
//to silence unused variable warnings
	cout << 
	AR_MAX << 
	AR_MAX_VAL<<
	dx[0]<<
	dy[1]<<
	PI<<
	EPS<<
	endl;
}
template<class Q>
typename Q::value_type pop(Q& q) {
    auto result = q.front();
    q.pop();
    return result;
};

//reading input the "java" way 
//(aka with method calls)
int pi() {
	int N;
	cin >> N;
	return N;
}
ll pl() {
	ll N;
	cin >> N;
	return N;
}
char pc() {
	char c;
	cin >> c;
	return c;
}
string ps() {
	string s;
	cin >> s;
	return s;
}


//other
template<class T1, class T2>
ll powf(T1 a, T2 b) {
	if(b<0)return 0;
	if (b == 0)return 1;
	ll val = powf(a, (ll)(b / 2));
	if (b & 1) {

		return ((val * val) % MOD * a) % MOD;
	} else {
		return (val * val) % MOD;
	}
}
string bin(int n, int digits) {
	string s = bitset<32>(n).to_string();
	s.erase(0, s.length() - digits);
	return s;
}
void IO(string fileName) {
	freopen((fileName + ".in").c_str(), "r", stdin);
	freopen((fileName + ".out").c_str(), "w", stdout);
}
ll cp(complex<ll> a, complex<ll> b){
	return (conj(a)*b).imag();
}
bool eq(double a, double b){
	return fabs(a-b)<=EPS;
}

/*

5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

1 1
R
 */
int main() {
	fast;
	int R = p;
	int C = p;
	char g[R][C];
	int dist[R][C]; fa(dist,0);
	dist[0][0] = 1;
	FR(r,R){
		FR(c,C){
			char cur = pc();
			g[r][c] = cur;
		}
	}
	deque<pii> q;
	q.push_back({0,0});
	int ans = 1;
	while(sz(q)){
		pii cur = q.front(); q.pop_front();
		FR(i,4){
			int r2 = cur.f+dx[i];
			int c2 = cur.s+dy[i];
			if(in(r2,R)&&in(c2,C)&&g[r2][c2]!='.'&&!dist[r2][c2]){

				if(g[r2][c2]==g[cur.f][cur.s]){
					dist[r2][c2] = dist[cur.f][cur.s];
					q.push_front({r2,c2});
				}else{
					dist[r2][c2] = dist[cur.f][cur.s]+1;
					q.push_back({r2,c2});

				}
				// cout<<r2<<" "<<c2<<endl;
				ans = max(ans,dist[r2][c2]);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void IO(std::string)':
tracks.cpp:118:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |  freopen((fileName + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:119:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |  freopen((fileName + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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