https://codeforces.com/contest/1472/problem/G
I keep getting MLE on this submimision. I just can’t figure out why especially since the ML is 256 megabytes.
#include <bits/stdc++.h>
#define db(x) if(0)cerr << #x <<":"<<x<<" "
using namespace std;
// ifstream fin (".in");
// ofstream fout(".out");
const int INF=1e9, MOD=1e9+7;
const int N=2e5+2;
unordered_set<int> g[N];
unordered_set<int> dag[N];
int best[N], special[N], d[N];
void dfsDag(int x){
special[x]=d[x];
for(int y:g[x]){
special[x]=min(special[x],d[y]);
if(d[y]>d[x]){
dag[x].insert(y);
dfsDag(y);
}
}
}
void dfsDp(int x){
for(int y:dag[x]){
dfsDp(y);
best[x]=min(best[x], best[y]);
}
best[x]=min(best[x], special[x]);
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i){
g[i].clear();
dag[i].clear();
}
fill(special+1, special+1+n, INF);
fill(best, best+1+n, INF);
fill(d, d+1+n, INF);
for(int i=m; i--;){
int x, y;
cin>>x>>y;
g[x].insert(y);
}
queue<int> q({1});
d[1]=0;
while(q.size()){
int x=q.front();
q.pop();
for(int y:g[x]){
if(d[x]+1<=d[y]){
q.push(y);
d[y]=d[x]+1;
}
}
}
dfsDag(1);
dfsDp(1);
for(int i=1;i<=n;++i)
cout<<best[i]<<" ";
cout<<"\n";
}
int main(){
#ifndef ONLINE_JUDGE
freopen("g.in", "r", stdin);
freopen("g.out", "w", stdout);
#endif
int t;
cin>>t;
while(t--){
solve();
}
}