Submission #1145996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145996		moaipo	Tracks in the Snow (BOI13_tracks)	C++20	82.50 / 100	2100 ms	116108 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> v;
vector<pair<int,int>> mv = {{0,1},{0,-1},{1,0},{-1,0}};

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin>>n>>m;
    v = vector<vector<int>> (n, vector<int>(m));
    auto odw = vector<vector<bool>> (n, vector<bool>(m));

    char c;
    for(int i=0;i<n;i++){
        for (int j = 0; j < m; ++j) {
            cin>>c;
            if(c=='R') v[i][j] = 1;
            else if(c=='F') v[i][j] = -1;
        }
    }

    priority_queue<vector<int>> q; // value, x, y
    q.push({-1,0,0});
    int maxi = 0;
    while(!q.empty()) {
        auto cur = q.top();
        q.pop();

        int val = cur[0], x= cur[1], y = cur[2], r = v[y][x];
        if(r==0) continue;
        for(auto &cm : mv) {
            int nx = x + cm.first, ny = y + cm.second;
            if(nx<0 || ny<0 || nx>=m || ny>=n) continue;
            if(odw[ny][nx]) continue;
            if(v[ny][nx] == -1 * r) {
                maxi = max(maxi, -(val-1));
                q.push({val-1, nx, ny});
            } else if(v[ny][nx] == r) {
                q.push({val, nx, ny});
            }
            odw[ny][nx] = true;
        }

        v[y][x] = 0; //odw
    }

    cout<<maxi<<'\n';
}

/*
 5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

 */

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