I used almost same approach but gave TLE in JAVA.
link
I did not see even one Accepted JAVA solution
1 Like
I was trying to do the same thing , got WA. Turns out the original problem is pretty straightforward.
Here is my simple approach -
I have initialized a vector of length n for storing 1 if the node is frozen and 0 if the node is not frozen and initialized with zeroes.
With the passing of each second of time, I do the following -
- I iterate through all the nodes and check if they are frozen or not
- For the nodes, which are not frozen, I start checking the neighbors of those nodes (simply iterating over the adjacency list of that node), and if I find a neighbor, which is marked, I put this node in the mark vector and break, thus moving to the next node.
- I have a mark vector that is initialized every second, which stores which nodes to mark after this second, as marking nodes directly in between seconds would be a problem.
- After iterating through all the nodes, I mark all the nodes in the mark vector as this second has now ended.
- now during the iteration of nodes, I keep a count to check whether all the nodes are already marked or not, and if all the nodes are already marked, there is no use of repeating this process for further coming seconds, and I use a global variable(like a flag, you can say), to break out to stop this process for further seconds.
My Submission Link - Solution: 60869964 | CodeChef
/*
add a check here if all the nodes are visited or not.
if all are visited then you don't have to run this loop.
*/
while (x-->0){
int size=frozen.size();
if(size==0)
break ;
while (size-->0){
int val = frozen.poll();
while (graph[val].size()>0){
int topVal=graph[val].poll();
isFrozen[topVal]=true;
frozen.add(topVal);
}
}
}
I am getting WA in Test Case 11 and 15 whats 's the problem ,can anyone help
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define Time cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define vi vector<int>
#define onesbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define sp(x, y) fixed << setprecision(y) << x
#define w(x) int x;cin >> x;while (x--)
#define tk(x) int x;cin >> x;
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
#define debug(x) cerr<< #x <<" ";_print(x);cerr<<endl;
#else
#define debug(x)
#endif
template <class T> void _print(T t){cerr<<t;}
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(vector < vector <T> > v){cerr<<"[\n";for(int l=0;l<v.size();l++){{for(int k=0;k<v[l].size();k++)cerr<<v[l][k]<<" ";}cerr<<"\n";}cerr<<"]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
class gcd{public:int g,t;};
int modularInverse(int a,int m){int z=(a%m+m)%m; return z; }
gcd extended_euclidean(int a,int b,int t1,int t2){ if(b==0){ gcd x; x.g=a; x.t=t1; return x; }int t=t1-t2*(int)(a/b);return extended_euclidean(b,a%b,t2,t);}
vector<int>v[300003];
void dfs(vector<bool>&affNeighbourNode,int node,int i,int d,vector<bool>&state,vector<int>&temp){
if(i>=d) {
temp.pb(node);
return;
}
for(auto x:v[node]){
if(state[x]==0){
state[x]=1;
dfs(affNeighbourNode,x,i+1,d,state,temp);
}
}
affNeighbourNode[node]=1;
}
int32_t main(){
fast
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen("error.txt","w",stderr);
#endif
int n,m,q;
cin>>n>>m>>q;
vector<bool>state(n+1,0);
vector<int>affecNode;
vector<bool>affNeighbourNode(n+1,0);
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=0;i<q;i++){
int type,x;
cin>>type>>x;
if(type==1){
if(affNeighbourNode[x]==0){
affecNode.push_back(x);
}
state[x]=1;
}
else if(type==2){
vector<int>temp;
for(auto z:affecNode){
if(affNeighbourNode[z]==1) continue;
else
dfs(affNeighbourNode,z,0,x,state,temp);
}
affecNode.clear();
affecNode=temp;
}
else{
if(state[x]==1) cout<<"YES\n";
else
cout<<"NO\n";
}
debug(state);
}
return 0;
}
Can anyone help me out like what i am doing wrong
my approach is simple I am using multi source bfs and marking all the nodes minimum time required by them to be frozen. for all the queries which needs to be answered i will check if the node was frozen before the curTime.I am storing the values of node(which needs to be answered) and curTime in req vector.After performing multi source bfs i am checking whethther i node is frozen or not and printing answer.(I am getting lot of wa please help me out below is my submission )
https://www.codechef.com/viewsolution/60885227
1 Like
If all nodes are visited then size will be zero just in next loop. So it will run just 1 extra time.
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.
1 Like
Oh fml, thanks for pointing it out, I really overlooked it during contest, and got 6-7 wa because of that xD
1 Like
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