Submission #951525

#	Time	Username	Problem	Language	Result	Execution time	Memory
951525		serpent_121	Tracks in the Snow (BOI13_tracks)	C++17	46.25 / 100	848 ms	340212 KiB

tracks

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <numeric>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;

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

int depth[4000][4000];

int main() {
    iostream::sync_with_stdio(false);
	cin.tie(0);
    ll h,w; cin >> h >> w;
    ll map[h][w];
    for (int i = 0; i< h; i++) {
        for (int j = 0; j<w; j++) {
            char k; cin >> k;
            if (k=='.') map[i][j] = 0;
            else if (k=='R') map[i][j] = 1;
            else map[i][j] = 2;
        }
    }
    deque<pair<ll,ll>> q; 
    q.push_back({0,0});
    depth[0][0] = 1;
    int maxdepth = 1;

    while (!q.empty()) {
        ll x= q.front().first; ll y = q.front().second; q.pop_front();
        for (int i = 0; i<4; i++) {
            if (x+dx[i]<w && x+dx[i]>=0 && y+dy[i]<h && y+dy[i]>=0 && map[x+dx[i]][y+dy[i]]!=0) {
                ll a = x+dx[i]; ll b = y+dy[i];
                maxdepth = max(maxdepth,depth[a][b]);
                if (map[a][b]==map[x][y] && depth[a][b]==0) {
                    q.push_front({a,b});
                    depth[a][b] = depth[x][y];
                }
                else {
                    if (depth[a][b]==0 || depth[a][b] > depth[x][y]+1) {
                        depth[a][b] = depth[x][y]+1; q.push_back({a,b});        
                    }
                }
            }
        }
    }

    cout << maxdepth;
}

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