oj.uz

Submission #1087415

# Submission time Handle Problem Language Result Execution time Memory
1087415 2024-09-12T16:06:14 Z sidlad Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 932 ms 321012 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1444 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 9 ms 1928 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 0 ms 452 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 6 ms 720 KB Output is correct
13 Correct 2 ms 600 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 14 ms 1232 KB Output is correct
16 Correct 16 ms 1440 KB Output is correct
17 Correct 8 ms 1032 KB Output is correct
18 Correct 10 ms 2012 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 43 ms 3552 KB Output is correct
3 Correct 285 ms 31848 KB Output is correct
4 Correct 65 ms 7616 KB Output is correct
5 Correct 164 ms 18028 KB Output is correct
6 Correct 932 ms 131940 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 44 ms 3680 KB Output is correct
14 Correct 24 ms 2352 KB Output is correct
15 Correct 15 ms 2440 KB Output is correct
16 Correct 28 ms 1596 KB Output is correct
17 Correct 105 ms 8584 KB Output is correct
18 Correct 86 ms 8276 KB Output is correct
19 Correct 57 ms 7616 KB Output is correct
20 Correct 59 ms 7228 KB Output is correct
21 Correct 195 ms 18764 KB Output is correct
22 Correct 150 ms 17888 KB Output is correct
23 Correct 230 ms 15792 KB Output is correct
24 Correct 135 ms 18256 KB Output is correct
25 Correct 244 ms 31828 KB Output is correct
26 Correct 542 ms 321012 KB Output is correct
27 Correct 616 ms 133872 KB Output is correct
28 Correct 845 ms 131908 KB Output is correct
29 Correct 791 ms 120592 KB Output is correct
30 Correct 714 ms 133252 KB Output is correct
31 Correct 759 ms 24008 KB Output is correct
32 Correct 580 ms 116000 KB Output is correct