Competitive Programming Solutions

1476D - Journey

29 Jan 2021 — Tags: dsu,graphs — URL

As the problem states, each country has two states (original roads and reversed roads). Let’s picture this with a bipartite graph, where each city has two corresponding nodes. For a given city $u$, let’s call its corresponding node on the original roads $id0(u)$ and $id1(1)$ on the reversed roads.

The ith road in this graph will connect $id0(i - 1)$ and $id1(i)$ if it’s a R road and $id0(i)$ and $id1(i - 1)$ otherwise.

Note that such edges can be considered undirected, since each time one edge is taken all of them should be reversed.

Using this, note that the answer of a given city $u$ is the size of the connected component that $id0(u)$ lies on.

We can use a dfs or a disjoint set union to compute this efficiently.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
vi solve(string s)
{
    int n = s.size();
    auto id0 = [](int u) { return 2 * u; };
    auto id1 = [](int u) { return 2 * u + 1; };
    atcoder::dsu dsu(2 * (n + 1));
    for (int i = 1; i <= n; ++i)
    {
        if (s[i - 1] == 'L')
            dsu.merge(id0(i), id1(i - 1));
        else
            dsu.merge(id0(i - 1), id1(i));
    }
    vi ans(n + 1);
    for (int i = 0; i <= n; ++i)
        ans[i] = dsu.size(2 * i);
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        string s;
        cin >> n >> s;
        auto ans = solve(s);
        for (auto x : ans)
            cout << x << " ";
        cout << endl;
    }
    return 0;
}

Related posts