Submission #753750

#	Time	Username	Problem	Language	Result	Execution time	Memory
753750		tiwerlol	Tracks in the Snow (BOI13_tracks)	C++14	84.69 / 100	2108 ms	166096 KiB

tracks

#include <iostream>
#include <map>
#include <climits>
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
#include <bitset>
#include <chrono>
#include <random>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

///ofstream cout("apm.out");
///ifstream cin("apm.in");

const int MOD = 1e9+7;

int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};

int mat[4001][4001];
int D[4001][4001];

void solve()
{
    int n, m; cin >> n >> m;

    for(int z = 0; z < n; z++)
    {
        string s; cin >> s;

        for(int x = 0; x < s.size(); x++)
        {
            if(s[x]=='.') mat[z+1][x+1] = 1;
            else if(s[x]=='R') mat[z+1][x+1] = 2;
            else mat[z+1][x+1] = 3;
            D[z+1][x+1] = 0;
        }
    }

    priority_queue<pair<int, pair<int, int>>> pQ;
    pQ.push(make_pair(1, make_pair(1, 1)));
    D[1][1] = 1;
    int ans = 1;

    while(!pQ.empty())
    {
        int val = -pQ.top().first, i = pQ.top().second.first, j = pQ.top().second.second;
        pQ.pop();

        for(int k = 0; k < 4; k++)
        {
            int ki = di[k] + i, kj = dj[k] + j;

            if((ki>=1&&ki<=n&&kj>=1&&kj<=m) && !D[ki][kj] && mat[ki][kj]!=1)
            {
                D[ki][kj] = D[i][j] + (mat[i][j]!=mat[ki][kj]);
                ans = max(D[ki][kj], ans);
                pQ.push(make_pair(-D[ki][kj], make_pair(ki, kj)));
            }
        }
    }
    cout << ans;
}

int main()
{
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int tt = 1; //cin >> tt;

    while(tt--)
        solve();
}

Compilation message (stderr)

tracks.cpp: In function 'void solve()':
tracks.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int x = 0; x < s.size(); x++)
      |                        ~~^~~~~~~~~~
tracks.cpp:52:13: warning: unused variable 'val' [-Wunused-variable]
   52 |         int val = -pQ.top().first, i = pQ.top().second.first, j = pQ.top().second.second;
      |             ^~~

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