1476D - Journey - CodeForces Solution

dfs and similar dp dsu implementation *1700

Please click on ads to support us..

Python Code: 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
            directions = input().strip()

    left = [i for i in range(n+1)]
    right = left.copy()

    for i in range(n-1, -1, -1):
        if directions[i:i+2] == 'RL':
            right[i] = right[i+2]
        elif directions[i] == 'R':
            right[i] = i+1

    for i in range(1, n+1):
        if directions[i-2:i] == 'RL':
            left[i] = left[i-2]
        elif directions[i-1] == 'L':
            left[i] = i-1

    ans = [1]*(n+1)
    for i in range(n+1):
        ans[i] += i-left[i] + right[i]-i

    print(*ans)

C++ Code: 

#include <bits/stdc++.h>
#define int long long
// make it faster
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;

string s; // example string: LRLRLR (L means left, R means right)
char T(char c)
{
    if (c == 'L')
        return 'R';
    if (c == 'R')
        return 'L';
}

void solve()
{
    int n;
    cin >> n;
    cin >> s;
    vector<vector<int>> graph(2 * n + 2);
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'L')
        {
            graph[i * 2 + 2].push_back(i * 2 + 1);
            graph[i * 2 + 1].push_back(i * 2 + 2);
        }
        else
        {
            graph[i * 2].push_back(i * 2 + 3);
            graph[i * 2 + 3].push_back(i * 2);
        }
    }

    vector<int> C(n * 2 + 2, -1);
    vector<int> q;

    for (int i = 0; i < 2 * n + 2; i++)
    {
        if (C[i] != -1)
            continue; // already visited
        int a = 1;
        int q_size = q.size();
        queue<int> Q;
        C[i] = q_size;
        Q.push(i);

        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            for (int v : graph[u])
            {
                if (C[v] == -1)
                {
                    a++;
                    C[v] = q_size;
                    Q.push(v);
                }
            }
        }

        q.push_back(a);
    }

    for (int i = 0; i <= n; i++)
    {
        cout << q[C[i * 2]] << " ";
    }
    cout << endl;
    return;
}

int32_t main()
{
    // fasio
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;

    cin >> q;
    while (q--)
    {
        solve();
    }

    return 0;
}


Comments

Submit
0 Comments
More Questions

580A- Kefa and First Steps
1472B- Fair Division
996A - Hit the Lottery
MSNSADM1 Football
MATCHES Playing with Matches
HRDSEQ Hard Sequence
DRCHEF Doctor Chef
559. Maximum Depth of N-ary Tree
821. Shortest Distance to a Character
1441. Build an Array With Stack Operations
1356. Sort Integers by The Number of 1 Bits
922. Sort Array By Parity II
344. Reverse String
1047. Remove All Adjacent Duplicates In String
977. Squares of a Sorted Array
852. Peak Index in a Mountain Array
461. Hamming Distance
1748. Sum of Unique Elements
897. Increasing Order Search Tree
905. Sort Array By Parity
1351. Count Negative Numbers in a Sorted Matrix
617. Merge Two Binary Trees
1450. Number of Students Doing Homework at a Given Time
700. Search in a Binary Search Tree
590. N-ary Tree Postorder Traversal
589. N-ary Tree Preorder Traversal
1299. Replace Elements with Greatest Element on Right Side
1768. Merge Strings Alternately
561. Array Partition I
1374. Generate a String With Characters That Have Odd Counts