Well, I missed the line where the graph was given as connected, but it didn’t make any real difference to my solution. I maintained a “front” of where the freezing had just happened - whether by spread or by initiation - and renewed it for each step of spread. Eventually the front becomes empty and I don’t need to do more updates. Of course already-frozen nodes do not get added to the front.
I think that the time constraint was bad for JAVA on this one …
can please tell me why my code is giving wrong answer and TLE in some cases.
I have taken reference from youtube video solution.
CODE-
#include <bits/stdc++.h>
using namespace std;
queue<int> q; // contain index to be frozen on next turn
void frozen_func(vector<int> &frozen, vector<int> arr[])
{
int n = q.size();
while (n--)
{
int cur = q.front();
if (frozen[cur])
{
continue;
}
else
{
frozen[cur] = 1;
}
q.pop();
for (int it : arr[cur])
{
q.push(it);
}
}
}
int main()
{
// your code goes here
int n, m, k;
cin >> n >> m >> k;
vector<int> arr[n + 1];
vector<int> frozen(n + 1);
queue<int> qq; // contain parent index which has been frozen on query 1 and whose neighbour has to be given to the q
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
arr[a].push_back(b);
arr[b].push_back(a);
}
int maxTime = n - 1; // max for every node to get frozen
while (k--)
{
int query, i;
cin >> query >> i;
if (query == 1)
{
if(!frozen[i])
{frozen[i] = 1;
qq.push(i);}
}
else if (query == 2)
{
while (!qq.empty())
{
int cur = qq.front();
qq.pop();
for (int it : arr[cur])
{
q.push(it);
}
}
if(q.empty() || maxTime==0) continue;
while (i-- && maxTime != 0)
{
frozen_func(frozen, arr);
maxTime--;
}
}
else
{
if (frozen[i])
{
cout << "YES\n";
}
else
{
cout << "NO\n";
}
}
}
return 0;
}
I am getting TLE only for subtask 3 Test case #19 even though mysolution has complexity O(Q+N+M).
Can someone please look at it?
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MK make_pair
#define F first
#define S second
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Os")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
const int MOD = 1e9 + 7;
int N,M,Q;
vector<vector<int>> g;
vector<int> f;
queue<int> nodes;
void bfs(int t)
{
if(t == 0 || nodes.size()==0)
return;
int n = nodes.size();
for(int i=0;i<n;i++)
{
int it = nodes.front();
f[it] = 1;
nodes.pop();
for(auto it1:g[it])
{
if(!f[it1])
{
f[it1] = 1;
nodes.push(it1);
}
}
}
bfs(t-1);
}
void solve()
{
cin >> N >> M >> Q;
g.resize(N+10);
f.resize(N+10,0);
while(!nodes.empty())
nodes.pop();
for(int i=0;i<M;i++)
{
int x,y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
while(Q--)
{
int n,c;
cin >> n >> c;
if(n == 1)
{
f[c] = 1;
nodes.push(c);
}
else if(n == 2)
bfs(c);
else
{
if(f[c])
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//Read and write to txt files
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int tc=1;
for (int t = 1; t <= tc; t++) {
solve();
}
}
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 same test-cases as yours : CodeChef: Practical coding for everyone
After that , I tried the simple bfs solution , which passed all the cases. Any idea why dijkstra solution fails ? @cherry0697 @iimda
here is my soln : CodeChef: Practical coding for everyone
Can’t figure out why getting WA, kindly provide me with any testcase if possible
here I used similar to bfs approach and my freeze array element i.e. freeze[i] can take any of the three values : -1, 0 and 1 with their meanings as follows :
-1 this node is unfrozen, since none of its’s neighbor nodes are frozen
0 means this node is in queue, since it has at least one frozen neighbor and we haven’t pushed this node’s unfrozen neighbors into the queue
1 means this node is frozen as well as we have pushed all its unfrozen neighbors into queue
rest of the logic is pretty similar to video editorial I guess.
void solve()
{
int n,m,q; cin>>n>>m>>q;
vector<int> adj[n+1];
while(m--)
{
int x,y; cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
queue<int> que;
vector<bool> visit(n+1,false);
while(q--)
{
int t1,t2; cin>>t1>>t2;
if(t1 == 1)
{
if(!visit[t2])
{
visit[t2] = true;
que.push(t2);
}
}
if(t1 == 2)
{
while(t2--)
{
int x = que.size();
while(x--)
{
int l= que.front();
que.pop();
for(int j : adj[l])
if(!visit[j])
{que.push(j); visit[j] = true;}
}
}
}
if(t1 == 3)
{
if(visit[t2])
cout<<"YES\n";
else
cout<<"NO\n";
}
}
}
Getting TLE on last 2 cases why?
Consider this test case.
Input
9 11 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
6 8
2 4
7 2
1 1
2 7
3 9
Expected Output
YES
Your Output
NO
Input Graph
After Query 1
After Query 2
So, for Query 3, the node 9 is frozen. It should be \text{YES} while you’re printing \text{NO}
I see… I got it why DFS is wrong. I wasn’t thinking of cycles in graph. That’s why. It seems like I am too used to trees now. Thank you so much. It was really insightful for me learn why this was wrong.
bro please help me out too i don’t think i have done mistake in thinking the solution
While there may be other issues, there is no guarantee that any freezing starts before some lengthy delay. Try the following test case:
3 3 7
1 2
2 3
1 3
2 999999999
2 999999999
1 1
2 2
3 1
3 2
3 3
Consider this test case
Input
5 6 3
1 2
2 3
3 4
4 5
5 3
5 1
2 2
3 5
1 5
Expected Output
NO
Your Output
YES
Given Graph
Hey, for queries of type 2, the values can be upto 10^9, and since your bfs function is recursive, it can be called upto 10^9 times in this case, which results in TLE.
Hey, there are cases where you are calling the frozen function to many times(possibly in the order of N), and since the frozen function has a while loop which run n times, the overall complexity can go upto O(n^2), that is causing the TLE
Hey @jhachirag7 
,
This is because of your DFS implementation for query 2 try to solve that using BFS for query 2 (just froze all t neighbours) This will not give TLE because Maximum of N-1 edges can be freeze so, Just check if you encounter a node which is neighbour of node N also it is not freeze then freeze it and add it to queue. Do this till “t” (query 2) times.
Hey @the_eagle_eye ,
Actually there can be almost N-1 edges that can be freeze with query 2 (because Graph is connected) thus your code is only freezing the nodes that are not froze yet. That’s why you are not getting TLE.
1 Like
Hey @abhinav_700 ,
Before the actual doubt we need to understand what code is saying. Firstly we are storing every node N with its time of appearance(P)(means when it was frozed).Because if we do that also we know total time passed so far (say T) then we can say that from node N we can move to exactly (T-P) distance far.Therefore when query 3 appear we will freeze all neighbours of every node. if req node is visited it means it is freeze thus answer is “YES” else “NO”.
Now purpose of priority queue is to maintain all nodes with their time of appearance.pushing with negative time of appearance makes priority queue to min heap(by default it is max heap).
So in Sim function we are actually freezing all nodes neighbours. Condition (x>t) tells us that if we encounter a neighbour that hai time of appearance greater than total time we have so we cannot freeze that node also as we maintain min heap all nodes after this node will also have time of appearance greater than total time thus we break it.
Hope you understand the editorial if not please do not hesitate to ask
Hey @abhinav_700
Thanks for asking your doubt.
You can use a single queue i.e q to solve the problem. When a new node is frozen you just push all the adjacent vertices of u into q instead of qq and mark the new node as frozen.
Hey @pranjal1223 ,
Your code is failing for the TC
5 6 3
1 2
2 3
3 4
4 5
5 3
5 1
2 2
3 5
1 5
Expected Output : NO
Your Output : YES
wow you are such a nice person 
. Thankyou for your reply and your humble gesture 