Submission #1087415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087415		sidlad	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	932 ms	321012 KiB

tracks

#include <bits/stdc++.h>
const long double EPS = 1e-7;
const long long int INF = LONG_LONG_MAX/2;
const long long int M = (long long int) 1e9 + 7;//998'244'353;
using namespace std;
//insert policy here

//insert mintcode here

#if defined (ONLINE_JUDGE) || !__has_include (</home/sidlad/Desktop/Coding Folder/c and cpp codes/Debug.h>)
    void _exe() {}
    template <typename T, typename... V>
    const T& _exe(const T &t,const V&... v) {return t;}
    template <typename T, typename... V>
    T& _exe(T &t,V&... v) {return t;}
    
    #define debug(x...) (_exe(x))
    
    class CNothing {};

    template <typename T>
    const CNothing& operator<<(const CNothing& proxy, const T&)
    {
        return proxy;
    }

    const CNothing& operator<<(const CNothing& proxy, std::ostream& (*)(std::ostream&))
    {
        return proxy;
    }
    CNothing cnothing;
    #define cerr cnothing
#else
    #include </home/sidlad/Desktop/Coding Folder/c and cpp codes/Debug.h>
#endif

#define int long long
#define double long double
#define all(x) (x).begin(),(x).end()
#define endl "\n" //comment out for interactive problems
#define cout(x) x?cout<<"Yes"<<endl:cout<<"No"<<endl

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cout.precision(numeric_limits<double>::max_digits10);
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    vector<pair<int,int>> dxy = {{-1,0},{1,0},{0,1},{0,-1}};

    int n,m;
    cin>>n>>m;
    vector<vector<char>> v(n,vector<char>(m));
    for(auto& row:v)for(auto& ele:row)cin>>ele;
    deque<pair<pair<int,int>,int>> dq;
    int ans = 1;
    dq.push_back({{0,0},1});
    while(dq.size())
    {
        auto [c,d] = dq.front();
        dq.pop_front();
        auto [i,j] = c;
        ans = max(ans,d);
        // debug(c,d);
        for(auto [dx,dy]:dxy)
        {
            int idx = i + dx;
            int jdy = j + dy;
            if(i + dx == -1 or i + dx == n)continue;
            if(j + dy == -1 or j + dy == m)continue;
            
            // debug(idx,jdy);
            if(v[idx][jdy] == '.')continue;
            if(v[idx][jdy] == v[i][j])dq.push_front({{idx,jdy},d});
            else dq.push_back({{idx,jdy},d + 1});

        }
        v[i][j] = '.';
    }
    cout<<ans<<endl;
}

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