oj.uz

Submission #831214

# Submission time Handle Problem Language Result Execution time Memory
831214 2023-08-19T23:20:02 Z Srivardhan_M Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 2000 ms 322484 KB 
	#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>   
using namespace std;


const long long infty = 1e18;
#define num1 1000000007
#define num2 998244353
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define repd(i,a,n) for(ll i=a; i>=n; i--)
#define pb push_back
#define pob pop_back
#define f first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define all(x) x.begin(), x.end()
#define M_PI 3.14159265358979323846
#define epsilon (double)(0.000000001)
#define popcount __builtin_popcountll
#define fileio(x) freopen("input.txt", "r", stdin); freopen(x, "w", stdout);
#define out(x) cout << ((x) ? "Yes" : "No")<<endl;
#define len(x) x.size()
#define vvll(vec,n,m) vector<vector<long long>> vec(n, vector<long long> (m))
#define start_clock() auto start_time = std::chrono::high_resolution_clock::now();
#define measure() auto end_time = std::chrono::high_resolution_clock::now(); cerr << (end_time - start_time)/std::chrono::milliseconds(1) << "ms" << endl;
#define println(x) cout<<x<<"\n";
 
 
typedef long long ll;
typedef long double ld;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;
typedef vector<pair<long long, long long>> vpll;
typedef vector<int> vii;

ll sqr(ll x){
    return x*x;
}

void print(vector<vll> &v){
    cout<<"=========================="<<endl;
    rep(i, 0, v.size()) {
        rep(j, 0, v[i].size()) cout<<v[i][j]<<" ";
        cout<<endl;
    }
    cout<<"=========================="<<endl;
}
void print(vll &v){
    cout<<"=========================="<<endl;
    rep(i, 0, v.size()) cout<<v[i]<<" ";
    cout<<endl;
    cout<<"=========================="<<endl;
}
ll n, m;

ll dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

ll inside(ll x, ll y, vector<string> &v){
    if(x<0 || x>=n || y<0 || y>=m || v[x][y] == '.') return 0;
    return 1;
}

void solve(){
    cin>>n>>m;
    vector<string> vec(n);
    rep(i,0,n) cin>>vec[i];
    vector<vll> d(n, vll(m, infty));
    d[0][0] = 0;
    deque<pll> q;
    q.push_back({0, 0});
    ll maxi = 0;
    while(!q.empty()){
        pll pr = q.front();
        ll u = pr.f;
        ll v = pr.s;
        maxi = max(maxi, d[u][v]);
        rep(i, 0, 4){
            ll x= u+dx[i];
            ll y = v+dy[i];
            if(!inside(x, y, vec)) continue;
            ll w = (vec[u][v] == vec[x][y])? 0: 1;
            if(d[u][v]+w < d[x][y]){
                d[x][y] = d[u][v]+w;
                if(w == 1) q.push_back({x, y});
                else q.push_front({x, y});
            }
        }
    }
    cout<<maxi+1<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // cin>>t;
    while(t--){
        solve();
    }
}

Compilation message

tracks.cpp: In function 'void print(std::vector<std::vector<long long int> >&)':
tracks.cpp:9:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,a,n) for(ll i=a;i<n;i++)
......
   42 |     rep(i, 0, v.size()) {
      |         ~~~~~~~~~~~~~~          
tracks.cpp:42:5: note: in expansion of macro 'rep'
   42 |     rep(i, 0, v.size()) {
      |     ^~~
tracks.cpp:9:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,a,n) for(ll i=a;i<n;i++)
......
   43 |         rep(j, 0, v[i].size()) cout<<v[i][j]<<" ";
      |             ~~~~~~~~~~~~~~~~~   
tracks.cpp:43:9: note: in expansion of macro 'rep'
   43 |         rep(j, 0, v[i].size()) cout<<v[i][j]<<" ";
      |         ^~~
tracks.cpp: In function 'void print(vll&)':
tracks.cpp:9:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,a,n) for(ll i=a;i<n;i++)
......
   50 |     rep(i, 0, v.size()) cout<<v[i]<<" ";
      |         ~~~~~~~~~~~~~~          
tracks.cpp:50:5: note: in expansion of macro 'rep'
   50 |     rep(i, 0, v.size()) cout<<v[i]<<" ";
      |     ^~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 2728 KB Time limit exceeded
2 Execution timed out 2075 ms 212 KB Time limit exceeded
3 Execution timed out 2059 ms 340 KB Time limit exceeded
4 Execution timed out 2073 ms 1748 KB Time limit exceeded
5 Execution timed out 2088 ms 1108 KB Time limit exceeded
6 Execution timed out 2083 ms 212 KB Time limit exceeded
7 Execution timed out 2078 ms 316 KB Time limit exceeded
8 Execution timed out 2082 ms 340 KB Time limit exceeded
9 Execution timed out 2072 ms 340 KB Time limit exceeded
10 Execution timed out 2068 ms 852 KB Time limit exceeded
11 Execution timed out 2037 ms 724 KB Time limit exceeded
12 Execution timed out 2072 ms 1108 KB Time limit exceeded
13 Execution timed out 2068 ms 1108 KB Time limit exceeded
14 Execution timed out 2064 ms 1108 KB Time limit exceeded
15 Execution timed out 2074 ms 2772 KB Time limit exceeded
16 Execution timed out 2083 ms 2636 KB Time limit exceeded
17 Execution timed out 2070 ms 2604 KB Time limit exceeded
18 Execution timed out 2067 ms 1748 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 980 KB Time limit exceeded
2 Execution timed out 2073 ms 15828 KB Time limit exceeded
3 Execution timed out 2020 ms 159192 KB Time limit exceeded
4 Execution timed out 2051 ms 37376 KB Time limit exceeded
5 Execution timed out 2044 ms 89548 KB Time limit exceeded
6 Execution timed out 2110 ms 159132 KB Time limit exceeded
7 Execution timed out 2063 ms 980 KB Time limit exceeded
8 Execution timed out 2067 ms 972 KB Time limit exceeded
9 Execution timed out 2075 ms 980 KB Time limit exceeded
10 Execution timed out 2060 ms 596 KB Time limit exceeded
11 Execution timed out 2069 ms 980 KB Time limit exceeded
12 Execution timed out 2073 ms 468 KB Time limit exceeded
13 Execution timed out 2036 ms 15752 KB Time limit exceeded
14 Execution timed out 2061 ms 9220 KB Time limit exceeded
15 Execution timed out 2050 ms 10196 KB Time limit exceeded
16 Execution timed out 2067 ms 6612 KB Time limit exceeded
17 Execution timed out 2065 ms 40456 KB Time limit exceeded
18 Execution timed out 2064 ms 39908 KB Time limit exceeded
19 Execution timed out 2075 ms 37324 KB Time limit exceeded
20 Execution timed out 2051 ms 34364 KB Time limit exceeded
21 Execution timed out 2017 ms 92564 KB Time limit exceeded
22 Execution timed out 2025 ms 89500 KB Time limit exceeded
23 Execution timed out 2043 ms 77024 KB Time limit exceeded
24 Execution timed out 2032 ms 90376 KB Time limit exceeded
25 Execution timed out 2094 ms 159308 KB Time limit exceeded
26 Execution timed out 2037 ms 322484 KB Time limit exceeded
27 Execution timed out 2093 ms 159436 KB Time limit exceeded
28 Execution timed out 2021 ms 159084 KB Time limit exceeded
29 Execution timed out 2023 ms 159232 KB Time limit exceeded
30 Execution timed out 2016 ms 155844 KB Time limit exceeded
31 Execution timed out 2031 ms 101896 KB Time limit exceeded
32 Execution timed out 2089 ms 159180 KB Time limit exceeded