Submission #831214

#	Time	Username	Problem	Language	Result	Execution time	Memory
831214		Srivardhan_M	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	2110 ms	322484 KiB

tracks

	#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 (stderr)

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
• Subtask 2: 0 / 70