Submission #1146089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146089		moaipo	Tracks in the Snow (BOI13_tracks)	C++20	86.88 / 100	1282 ms	1114112 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));

    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;
        }
    }

    vector<vector<int>> nq (n*m);
    vector<vector<int>> q(n*m); // x, y
    q[0] = {0,0};
    int maxi = 0;
    bool a = true;
    int i = 0;
    int sizq=1, siznq=0;
    while(true) {
        int ssiz = a ? sizq : siznq;
        if(i >= ssiz) break;
        for(;i<ssiz;i++) {
            auto cur = a ? q[i] : nq[i];
            int x = cur[0], y = cur[1], r = v[y][x];
            if(r==0) continue;
            if(abs(r)==2) r/=2;
            for(auto &cm : mv) {
                int nx = x + cm.first, ny = y + cm.second;
                if(nx<0 || ny<0 || nx>=m || ny>=n) continue;
                int nr = v[ny][nx];
                if(nr == 0 || nr == 2 || nr == -2) continue;
                if(nr == -r) {
                    if(a) {
                        nq[siznq] = {nx, ny};
                        siznq++;
                    }
                    else {
                        q[sizq] = {nx, ny};
                        sizq++;
                    }
                } else if(nr == r) {
                    if (a) {
                        q[sizq] = {nx, ny};
                        sizq++;
                    } else {
                        nq[siznq] = {nx, ny};
                        siznq++;
                    }
                    ssiz++;
                }
                v[ny][nx] = 2*nr;
            }
            v[y][x] = 0;
        }
        if(a) {
            sizq = 0;
            i = 0;
        }
        else {
            siznq = 0;
            i = 0;
        }
        a = !a;
        maxi++;
    }

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

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

 */

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