Submission #1215669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215669		behesht	Tracks in the Snow (BOI13_tracks)	C++20	80.31 / 100	2140 ms	1114112 KiB

tracks

#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define ld                   long double
#define ll                   long long
#define pb                   push_back
#define arr(x)               array <ll, x>
#define endl                 '\n'
#define int                  long long

using namespace std;

const int INF = 1e9 + 24 + (33 / 10); // 33 ---> 34
const int MAXN = 4e3 + 24 + (33 / 10); // 33 ---> 34

int dx[2] = {-0, -1};
int dy[2] = {-1, -0};

int a[MAXN][MAXN];
int dis[MAXN][MAXN];
vector <arr(3)> adj[MAXN][MAXN];

signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){

            char eli;
            cin >> eli;

            if(eli == 'F')
                a[i][j] = 1;

            else if(eli == 'R')
                a[i][j] = 2;
            
            else 
                continue;
            
            for(int k = 0; k < 2; k++){

                int nx = i + dx[k];
                int ny = j + dy[k];

                if(!a[nx][ny])
                    continue;
                
                if(a[nx][ny] == a[i][j]){
                    adj[nx][ny].pb({i, j, 0});
                    adj[i][j].pb({nx, ny, 0});
                }

                else{
                    adj[nx][ny].pb({i, j, 1});
                    adj[i][j].pb({nx, ny, 1});
                }

                // d4(i, j, nx, ny);
            }
        }
    }

    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= m; j++)
            dis[i][j] = INF;

    deque <arr(2)> q;
    q.push_front({1, 1});
    dis[1][1] = 0;
    int ans = 0;

    while(!q.empty()){

        auto [ux, uy] = q.front();
        q.pop_front();
        ans = max(ans, dis[ux][uy]);
        
        for(auto [vx, vy, w] : adj[ux][uy]){

            if(dis[vx][vy] > dis[ux][uy] + w){

                dis[vx][vy] = dis[ux][uy] + w;

                if(w)
                    q.pb({vx, vy});
                
                else 
                    q.push_front({vx, vy});
            }
        }
    }

    cout << ans + 1 << endl;
}

// Man hamooonam ke ye rooz...

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