Can anyone tell me what is the difference between these 2 if-statements?
Submission link: CodeChef: Practical coding for everyone
Submission link: CodeChef: Practical coding for everyone
I am getting ac on first and wa on the second one… don’t know why
In the first snippet, you’re checking only the type of query inside if. But in the second snippet, you’re also checking another condition !popped[x - 1]. This will impact the flow of control. Consider a case where t == 1 is true but !popped[x - 1] is false. In this case, the control will not enter both if and else if. Instead, it will enter else which is not what we want. You should also make sure that the control enters else only when t = 3.
Oh fml, thanks for pointing it out, I really overlooked it during contest, and got 6-7 wa because of that xD
in the video editorial , i have noticed that they are using two queues: qq and q. Can anyone explain why can’t we use just one of them ?
I have some doubts
what exactly is the purpose of priority queue pq? and why are we pushing -t as its first element instead of pushing t simply
why do we need the condition of x> t in the sim function? I can’t understand how it is working
Was it guaranteed that no two u, v will be the same in input? no.
I did this problem by just using two unordered sets instead of a queue but I have used a map to ensure distinct u,v pair (gives tle). After removing that map solution gets ac.
Can someone give the wrong test case for my solution? @admin
Link: CodeChef: Practical coding for everyone
It is passing all the test cases except two. My approach is very different, so I want to know where is the mistake in my solution.
@suman_18733097 Please let me know the wrong test case. I am not able to get why using the dfs approach is wrong.
The solution is pretty cool. Faster and cleaner than what I was doing.
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
