Submission #1307960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307960		kyryl	Tracks in the Snow (BOI13_tracks)	C++20	31.77 / 100	1154 ms	891512 KiB

tracks

#include <bits/stdc++.h>
#define un unsgined
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define all(v) begin(v), end(v)
#define st first
#define nd second
using ll = long long;
using bigi = __int128;
using namespace std;
const int N = 4005;
vector<pair<int, int>> ruch{
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0}
};
int tab[N][N];
int gle[N][N];
bool byl[N][N];
void zaz(int ii, int jj){
    for(auto [x, y] : ruch){
        if(tab[ii + x][jj + y] == tab[ii][jj] && !gle[ii + x][jj + y]){
            gle[ii + x][jj + y] = gle[ii][jj];
            zaz(ii + x, jj + y);
        }
    }
}
void dalej(int ii, int jj){
    for(auto [x, y] : ruch){
        if(!tab[ii + x][jj + y]) continue;
        if(tab[ii + x][jj + y] == tab[ii][jj]){
            if(byl[ii + x][jj + y]){
                continue;
            }
            byl[ii + x][jj + y] = true;
            dalej(ii + x, jj + y);
        }
        else{
            if(gle[ii + x][jj + y]) continue;
            gle[ii + x][jj + y] = gle[ii][jj] + 1;
            zaz(ii + x, jj + y);
            dalej(ii + x, jj + y);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    rep(i, 1, n + 1){
        rep(j, 1, m + 1){
            char c;
            cin >> c;
            if(c == '.') tab[i][j] = 0;
            else if(c == 'F') tab[i][j] = 1;
            else tab[i][j] = 2;
        }
    }
    gle[1][1] = 1;
    byl[1][1] = 1;
    zaz(1, 1);
    dalej(1, 1);
    int maks = 0;
    rep(i, 1, n + 1){
        rep(j, 1, m + 1){
            maks = max(maks, gle[i][j]);
        }
    }
    cout << maks << '\n';
}

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