Submission #101415

#	Time	Username	Problem	Language	Result	Execution time	Memory
101415		SomeoneUnknown	Tracks in the Snow (BOI13_tracks)	C++14	80.31 / 100	2073 ms	215756 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ii mii(int b, int c){
    return make_pair(b,c);
}

iii miii(int a, int b, int c){
    return make_pair(a, mii(b,c));
}

int main(){
    ios_base::sync_with_stdio(false);
    int r, c;
    cin >> r >> c;
    string m[r];
    for(int i = 0; i < r; i++){
        cin >> m[i];
        //cout << "read";
    }
    priority_queue<iii> vable;
    vable.push(miii(-1, 0, 0));
    vable.push(miii(-1, r-1, c-1));
    int most = 0;
    while(!vable.empty()){
        iii ving = vable.top();
        vable.pop();
        int y = ving.second.first;
        int x = ving.second.second;
        if(m[y][x] == '.') continue;
        int a = ving.first;
        most = max(most, -a);
        if(y != r-1){
            vable.push(miii(a-(m[y][x]!=m[y+1][x]), y+1, x));
        }
        if(x != c-1){
            vable.push(miii(a-(m[y][x]!=m[y][x+1]), y, x+1));
        }
        if(y != 0){
            vable.push(miii(a-(m[y][x]!=m[y-1][x]), y-1, x));
        }
        if(x != 0){
            vable.push(miii(a-(m[y][x]!=m[y][x-1]), y, x-1));
        }
        m[y][x] = '.';
    }
    cout << most;//*/
}
/*
5 8
FFRF....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/

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