Submission #961951

#	Time	Username	Problem	Language	Result	Execution time	Memory
961951		marinaluca	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	600 ms	239240 KiB

tracks

#include <bits/stdc++.h>
 
#pragma GCC optimize ("O4")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
 
using namespace std;
#define int long long
#define ll long long
#define XX first
#define YY second
#define all (x) begin(x), end(x)
/**
#define cin fin
#define cout fout
ifstream cin ("pfn.in");
ofstream cout ("pfn.out");
**/
typedef double dbl;
typedef long double ldb;
typedef pair <int, int> pii;
typedef vector <int> vii;
typedef pair <double, int> pdi;

const int SMAX = 10;
const int VMAX = 1;
const int RMAX = 179;
const int NMAX = 4e3;

int n, m;
char v[NMAX + 1][NMAX + 1];
int matrix[NMAX + 1][NMAX + 1];
struct elem {
    int x, y;
};

void read(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i){
        for (int j = 1; j <= m; ++ j){
            cin >> v[i][j];
        }
    }
}

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool outmat (const elem &a){
    return a.x < 1 || a.x > n || a.y < 1 || a.y > m;
}

void solve (){
    int maxi = 1;
    matrix[1][1] = 1;
    deque <elem> pq;
    pq.push_front({1, 1});
    while (!pq.empty()){
        elem val = pq.front();
        pq.pop_front();
        maxi = max (maxi, matrix[val.x][val.y]);
        for (int i = 0; i < 4; ++ i){
            elem s = {val.x + dx[i], val.y + dy[i]};
            if (!outmat(s) && matrix[s.x][s.y] == 0 && v[s.x][s.y] != '.'){
                if (v[s.x][s.y] == v[val.x][val.y])
                {
                    matrix[s.x][s.y] = matrix[val.x][val.y];
                    pq.push_front(s);
                }
                else
                {
                    matrix[s.x][s.y] = matrix[val.x][val.y] + 1;
                    pq.push_back(s);
                }
            }
        }
    }
    cout << maxi;
}
signed main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int query = 1;
    while (query --){
        read();
        solve();
    }
    return 0 ^ 0;
}

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