Submission #1120286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120286		HasanV11010238	Tracks in the Snow (BOI13_tracks)	C++17	75.94 / 100	2191 ms	1048576 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long long
#define INF 1000000000
vector<vector<vector<int>>> v;
int bfs(int n, int st){
    try{
        vector<int> di(n, INF);
        deque<int> q;
        di[st] = 0;
        q.push_back(st);
        while (!q.empty()){
            int x = q.front();
            q.pop_front();
            for (auto el : v[x]){
                if (di[el[0]] > di[x] + el[1]){
                    di[el[0]] = di[x] + el[1];
                    if (el[1] == 0){
                        q.push_front(el[0]);
                    }
                    else{
                        q.push_back(el[0]);
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++){
            if (di[i] == INF) continue;
            ans = max(ans, di[i]);
        }
        return ans;
    }
    catch(int exc){
        return -1;
    }
}
int main(){
    try{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int n, m;
        cin>>n>>m;
        v.resize((n + 1) * (m + 1));
        vector<string> s(n);
        for (int i = 0; i < n; i++){
            cin>>s[i];
            for (int j = 0; j < m; j++){
                if (s[i][j] == '.') continue;
                int v1 = i * m + j;
                if (i != 0 && s[i - 1][j] != '.'){
                    int v2 = (i - 1) * m + j;
                    int va;
                    if (s[i][j] == s[i - 1][j]){
                        va = 0;
                    }
                    else{
                        va = 1;
                    }
                    v[v1].push_back({v2, va});
                    v[v2].push_back({v1, va});
                }
                if (j != 0 && s[i][j - 1] != '.'){
                    int v2 = i * m + j - 1;
                    int va;
                    if (s[i][j] == s[i][j - 1]){
                        va = 0;
                    }
                    else{
                        va = 1;
                    }
                    v[v1].push_back({v2, va});
                    v[v2].push_back({v1, va});
                }
            }
        }
        cout<<bfs(n * m, 0) + 1;
    }
    catch(int exc){
        cout<<-1;
    }
}

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