Hello everyone,

I have recently started to learn about graph theory and studied DFS and BFS. I was solving E — Shortest Path

The approach I thought

First put all the blocked roads into a set of triplets, then do a BFS with a condition. The condition was, before adding the adjacent nodes of the current node in the queue just check if its parent and parent's parent i.e. Let's say we have visited A -> B and now we have a child C then check if this triplet (A, B, C) is present in the set or not. If it does than do not visit the node C and continue with the other adjacent nodes of node B other than C.

The problem I am facing is, with the third test case. As this approach is not the right one, it is not reaching at the end for the last test case. i.e.

4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4

The valid path for this test case is 1 -> 3 -> 2 -> 3 -> 4 but I am getting -1.

Here is what I have implemented — Code

I have spent more than an hour but not getting any idea how can I visit the nodes as in the last case.

Am I required to learn any new algo? Any hints will be appreciated.

Thank you :)

Hello everyone!

Today I found a weird thing. I was solving problem C from Educational Codeforces Round 115. The link for the same is here. 1598C - Удаление двух элементов I have solved this problem using map. The link to my solution using map is here: map solution But it was consuming more time. So I decided to reduce it. Then I realized that I actually do not want the ordered map. So, I have just replaced map with unordered_map. The link to my solution using unordered_map is here: unordered_map solution But surprisingly, I got TLE on test case 14. I don't know the reason behind this. Can anyone explain me why this happened?

Thank you :)

Hello, everyone! I was learning Segment Tree and was trying problems on CSES. I came across the following problem — CSES — Task — 1647.

Problem Statement
Given an array of $$$n$$$ integers, your task is to process $$$q$$$ queries of the form: what is the minimum value in range $$$[a,b]$$$?

INPUT
The first input line has two integers $$$n$$$ and $$$q$$$: the number of values and queries.
The second line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the array values.
Finally, there are $$$q$$$ lines describing the queries. Each line has two integers $$$a$$$ and $$$b$$$. What is the minimum value in range $$$[a,b]$$$?

OUTPUT
Print the result of each query.

Constraints
$$$1 \le n,q \le 2 \cdot 10^5$$$
$$$1 \le x_i \le 10^9$$$
$$$1 \le a \le b \le n$$$

Following is my submission to this problem

// ====================================
// Template by Taukirahmed Khatri
// ====================================
 
#include "bits/stdc++.h"
using namespace std;
 
#define fast_io                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
 
typedef long long ll;
#define vi vector<ll>
#define pb push_back
 
#define nl "\n"
#define print(a)          \
    for (auto &i : a)     \
        cout << i << " "; \
    cout << nl
#define yesno(x) cout << (((x)) ? "YES" : "NO") << nl
#define cntdig(x) floor(log(x) + 1)
 
#define fra(i, init, n, inc) for (i = init; i < n; i += inc)
#define frd(i, init, n, dec) for (i = init; i >= n; i -= dec)
 
bool sortbysec(pair<int, int> &a, pair<int, int> &b)
{
    return a.second < b.second;
}
 
void tv(vi &a, ll n)
{
    ll i = 0;
    fra(i, 0, n, 1)
    {
        ll t;
        cin >> t;
        a.pb(t);
    }
}
 
class segment_tree
{
    vector<ll> sg;
    ll n;
 
public:
    segment_tree(ll dn)
    {
        n = dn;
        sg.resize(4 * n);
    }
 
    void build(vector<ll> a, ll start, ll end, ll cur_node)
    {
        if (start == end)
        {
            sg[cur_node] = a[start];
            return;
        }
        ll mid = (start + end) / 2;
        build(a, start, mid, 2 * cur_node);
        build(a, mid + 1, end, 2 * cur_node + 1);
        sg[cur_node] = min(sg[2 * cur_node], sg[2 * cur_node + 1]);
    }
 
    ll query(ll start, ll end, ll cur_node, ll left, ll right)
    {
        if (end < left || start > right)
            return LONG_MAX;
 
        if (start >= left && end <= right)
            return sg[cur_node];
 
        ll mid = (start + end) / 2;
        ll lres = query(start, mid, 2 * cur_node, left, right);
        ll rres = query(mid + 1, end, 2 * cur_node + 1, left, right);
        return min(lres, rres);
    }
};
 
void my_sol()
{
    ll n, q;
    cin >> n >> q;
    vi a;
    tv(a, n);
    segment_tree s(n);
    s.build(a, 0, n - 1, 1);
    vi ans;
    for (ll i = 0; i < q; i++)
    {
        ll l, r;
        cin >> l >> r;
        ans.push_back(s.query(0, n - 1, 1, l - 1, r - 1));
    }
    for (auto i : ans)
        cout << i << endl;
}
 
int main()
{
    fast_io;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    auto start = std::chrono::high_resolution_clock::now();
#endif
 
    // ll t;
    // cin >> t;
    // while (t--)
    my_sol();
 
#ifndef ONLINE_JUDGE
    auto stop = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    long double t1 = (long double)duration.count() / 1000000;
    cout << "\n\nTime taken " << fixed << setprecision(6) << t1 << " seconds ";
#endif
    return 0;
}

I don't know why it is giving TLE. Any idea? I was searching for a better solution. But sadly I failed. Hope from here, I will get some hints. Thank you :)