Having doubts and Getting wrong answer for ELWINTER problem from MARCH LUNCHTIME

help
1

i have copy pasted this code from editorial , but it is giving me wrong answer for the given test cases and i am also having some doubts regarding the approach which is discussed in the editorial . Can Somebody Help?

Doubt
why do we need two queues i.e. qq and q? what is their purpose?

Code:-

#include "bits/stdc++.h"
#define ll long long int
#define MOD 1000000007
using namespace std;

void frozeAdj(vector<vector<ll>> &graph, queue<ll> &q, vector<ll> &arr)
{
    ll rep = q.size();
    while (rep--)
    {
        auto i = q.front();
        q.pop();
        if (arr[i])
            continue;
        arr[i] = 1;

        for (ll j : graph[i])
            q.push(j);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin >> t;
    while (t--)
    {
        ll n, m, query;
        vector<ll> arr(n + 1, 0); // array for tracing if node is frozen
        queue<ll> q;              // to implement frozeAdjacent function
        vector<vector<ll>> graph(n + 1);
        cin >> n >> m >> query;

        for (ll i = 0; i < m; i++)
        {
            ll a, b;
            cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        ll mxtimes = n - 1;
        queue<ll> qq;
        while (query--)
        {
            ll a, b;
            cin >> a >> b;
            if (a == 1)
            {
                if (!arr[b])
                {
                    qq.push(b);
                    arr[b] = 1;
                }
            }

            else if (a == 2)
            {
                while (!qq.empty())
                {
                    ll i = qq.front();
                    qq.pop();
                    for (ll j : graph[i])
                        q.push(j);
                }

                if (q.empty() || mxtimes == 0)
                    continue;

                while (b-- && mxtimes > 0)
                {
                    frozeAdj(graph, q, arr);
                    mxtimes--;
                }
            }

            else
            {
                if (arr[b])
                    cout << "YES" << endl;
                else
                    cout << "NO" << endl;
            }
        }
    }
    return 0;
}
2

The two queues are essential for the proper state-transition from time T to time T+1.

Check the following accepted code .

Accepted

3

Can you tell why is the Dijkstra based solution failing ? All that was done is , added. extra edges from source node(node which was frozen before all others) to other nodes which are getting froze at later timings , and edge weight = (time of source node - time of other node) , solution is failing : CodeChef: Practical coding for everyone

After that , I tried the simple bfs solution , which passed (passed) all the cases. Any idea why dijkstra solution fails ? @codingknight

4

I am not able to understand

5

Check the following update to your Dijkstra based solution.

Accepted