Submission #639539

#	Time	Username	Problem	Language	Result	Execution time	Memory
639539		AdiCoder03	Tracks in the Snow (BOI13_tracks)	C++17	80.31 / 100	2059 ms	1048576 KiB

tracks

#include<bits/stdc++.h>
typedef long long ll;

#define vi vector<int>
#define pb push_back
#define self_min(a, b) a = min(a, b)
#define self_max(a, b) a = max(a, b)
#define V vector
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define fs(lcv, hi) for(lcv = 0; lcv < hi; lcv ++)
#define fb(lcv, hi) for(lcv = hi; lcv >= 0; lcv --)
#define loop(lcv, lower, upper) for(lcv = lower; lcv < upper; lcv++)
#define crd(pii) [pii.first][pii.second]

using namespace std;

V<vi> grid;
V<V<V<pair<int, pair<int, int>>>>> adj;
V<V<bool>> vis;
V<V<int>> distances;
int h, w;

void flood_fill(int x, int y);

void process(int x1, int y1, int x2, int y2)
{
    if(x1 < 0 || x1 > h - 1 || y1 < 0 || y1 > w-1 || !grid[x1][y1]) return;
    if(grid[x1][y1] == grid[x2][y2])
    {
        adj[x1][y1].pb({0, {x2, y2}});
        adj[x2][y2].pb({0, {x1, y1}});
    }
    else
    {
        adj[x1][y1].pb({1, {x2, y2}});
        adj[x2][y2].pb({1, {x1, y1}});
    }
    if(!vis[x1][y1])
    flood_fill(x1, y1);
}

void flood_fill(int x, int y)
{
    vis[x][y] = 1;
    process(x - 1, y, x, y);
    process(x, y - 1, x, y);
    process(x + 1, y, x, y);
    process(x, y + 1, x, y);
}

int find_max(int x, int y)
{
    deque<pair<int, int>> bfsq;
    bfsq.push_back({x, y});
    distances[x][y] = 0;
    int res = 0;
    while(!bfsq.empty())
    {
        pair<int, int> tp = bfsq.front();
        bfsq.pop_front();
        // vis[tp.first][tp.second] = 1;
        for(auto x : adj crd(tp))
        {
            if(distances crd(x.second) > distances crd(tp) + x.first)
            {
                distances crd(x.second) = distances crd(tp) + x.first;
                if(x.first) bfsq.push_back(x.second);
                else bfsq.push_front(x.second);
                self_max(res, distances crd(x.second));
                // vis crd(x.second) = 1;
            }
        }
    }
    return res;
}

void solve()
{
    int i, j;
    cin >> h >> w;
    grid.assign(h, vi(w, 0));
    vis.assign(h, V<bool> (w, 0));
    adj.assign(h, V<V<pair<int, pair<int, int>>>>(w));
    fs(i, h)
    {
        string row;
        cin >> row;
        fs(j, w)
        {
            if(row[j] == 'F') grid[i][j] = 1;
            else if(row[j] == 'R') grid[i][j] = 2;
        }
    }
    flood_fill(0, 0);
    distances.assign(h, vi(w, (int)1e9));
    cout << 1 + find_max(0, 0) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

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