PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Voicu Mihai
Tester: Manan Grover
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy
PREREQUISITES:
BFS, Graphs
PROBLEM:
You are given a connected graph with N nodes and M edges. You are given Q queries of the following types:
- đťź· u: Given node u(1\le u \le N), set the state of the node u to frozen.
- 𝟸 𝚝: Given t, let t units of time pass by
- đťźą đťšź: Given node v (1 \le v \le N), answer if node v is currently frozen.
Initially, no node is frozen.
The graph has the following property:
- If, at time T, a node u is frozen, then, at time (T+1), all neighbours of u become frozen.
For each query of type 3, answer whether the node is currently frozen.
EXPLANATION:
Let us first see that the graph is connected, hence if you look at the 2^{nd} type of the query then you can realize that the if the any node is frozen at time x then the whole graph will get frozen at x+N-1 seconds at maximum because of the only single reason that the graph is connected.
Hence you need not to be afraid of such large constraints for the second query. Now as the problem says you need to do that and it’s a simple BFS.
While writing the editorial I remembered the analogy used by CP algorithms to explain BFS when I was new to BFS. I will paste that analogy and you will find it interesting as it’s what our question says:
“The algorithm can be understood as a fire spreading on the graph: at the zeroth step only the source s is on fire. At each step, the fire burning at each vertex spreads to all of its neighbors. In one iteration of the algorithm, the “ring of fire” is expanded in width by one unit (hence the name of the algorithm).”
They used this analogy to explain BFS and here are we our question is this analogy isn’t that. Hence we will be using BFS for the same. Now let’s see how we will be dealing with the queries.
-
1^{st} type of Query.
For this type of query you will be given a node which we want you to froze that. If the node is already frozen sorry for the query, you can forgave us. But if its not frozen just froze that and add to the queue.
-
2^{nd} type of Query.
For this type of query, as we told you need to perform the bfs till the current time to the given time. But remember you after a certain interval of time every node will get frozen and you can stop performing bfs after that and can simply ignore these type of queries from then.
-
3^{rd} type of Query.
For this type of query please check if the node is frozen and let us know. Thanks for your help.
TIME COMPLEXITY:
O(Q + N + M)
SOLUTIONS:
Setter
#include <bits/stdc++.h>
using namespace std;
const int nmax = 3e5 + 5;
vector<int> g[nmax];
int frozen[nmax];
queue<pair<int,int> > que; // I used this to ensure that timelimits won't be against the use of the std::queue, although I know it is preffered to hand-write the queue
int currenttime;
static void timepass() {
while(!que.empty()) {
int t, x;
tie(t, x) = que.front();
if(t > currenttime)
break;
que.pop();
for(auto y : g[x]) {
if(frozen[y])
continue;
que.push({t + 1, y});
frozen[y] = 1;
}
}
currenttime++;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
for(int i = 0,x, y; i < m; i++) {
cin >> x >> y;
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 0; i < q; i++) {
int t, x;
cin >> t >> x;
if(t == 1) {
--x;
if(frozen[x] == 0)
frozen[x] = 1, que.push({currenttime, x});
}
if(t == 2) {
x = min(n + 1, x + currenttime);
while(currenttime < x)
timepass();
}
if(t == 3) {
--x;
cout << (frozen[x]? "YES\n" : "NO\n");
}
}
return 0;
}
Tester
#include <bits/stdc++.h>
using namespace std;
void sim(priority_queue<pair<int, int>> &pq, int vis[], int t, vector<int> gr[]){
while(pq.size()){
int x = -pq.top().first;
int y = pq.top().second;
if(x > t){
break;
}
pq.pop();
if(vis[y] != -1){
continue;
}
vis[y] = x;
for(int i = 0; i < gr[y].size(); i++){
pq.push({-x - 1, gr[y][i]});
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, m, q;
cin>>n>>m>>q;
vector<int> gr[n + 1];
for(int i = 0; i < m; i++){
int u, v;
cin>>u>>v;
gr[u].push_back(v);
gr[v].push_back(u);
}
int vis[n + 1];
memset(vis, -1, sizeof(vis));
priority_queue<pair<int, int>> pq;
int t = 0;
bool f = false;
while(q--){
int x, y;
cin>>x>>y;
if(x == 1){
pq.push({-t, y});
}
if(x == 2){
t += y;
}
if(x == 3){
sim(pq, vis, t, gr);
if(vis[y] == -1){
cout<<"NO\n";
}else{
cout<<"YES\n";
}
}
}
return 0;
}