Submission #856952

#	Time	Username	Problem	Language	Result	Execution time	Memory
856952		teesla	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1061 ms	135836 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4005;
typedef pair<int,int> ii;
typedef pair<int, ii> iii;

int adj[maxn][maxn], vis[maxn][maxn];
int vx[4] = {0,1,0,-1}, vy[4] = {1,0,-1,0};
int h,w;


int dijkstra(){

    queue<ii> zero,um;

    zero.push({h,w});
    vis[h][w] = 1;
    int res = 0;

    while(!zero.empty()){

        res++;

        while(!zero.empty()){

            auto [a,b] = zero.front();
            zero.pop();

            if(vis[a][b] < res) continue;

            for(int i=0; i<4; i++){

                int xx = a + vx[i], yy = b + vy[i];

                if(adj[xx][yy] == 0) continue;

                int val = vis[a][b];

                if(adj[xx][yy] != adj[a][b]){
                    val ++;
                }

                if( vis[xx][yy] != 0 and vis[xx][yy] <= val) continue;

                vis[xx][yy] = val;

                if(val == res) zero.push({xx,yy});
                else um.push({xx,yy});
            }

        }



        swap(zero,um);
    }

    
    return res;
}

int main(){

     cin >> h >> w;


    for(int i=1; i<=h; i++){

        string s; cin >> s;

        for(int j =0; j<w; j++){

            int val = 0;
            if(s[j] == 'R') val = 1;
            else if(s[j] == 'F') val = 2;

            adj[i][j+1] = val;
        }

    }


    cout << dijkstra() << endl;
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int dijkstra()':
tracks.cpp:26:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |             auto [a,b] = zero.front();
      |                  ^

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