Problem : Link. I simply did bfs from node 1 and found the maximum distance from this node to all other nodes
Code
So the solution is O(n+m) but still, there is TLE in one case. Why?
# | User | Rating |
---|---|---|
1 | Benq | 3783 |
2 | jiangly | 3666 |
3 | tourist | 3611 |
4 | Um_nik | 3536 |
5 | inaFSTream | 3477 |
6 | fantasy | 3468 |
7 | maroonrk | 3464 |
8 | QAQAutoMaton | 3428 |
9 | ecnerwala | 3427 |
10 | Ormlis | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 184 |
2 | adamant | 178 |
3 | awoo | 177 |
4 | nor | 169 |
5 | maroonrk | 165 |
6 | -is-this-fft- | 163 |
7 | antontrygubO_o | 152 |
7 | ko_osaga | 152 |
9 | dario2994 | 150 |
10 | SecondThread | 149 |
Problem : Link. I simply did bfs from node 1 and found the maximum distance from this node to all other nodes
const int INF = 1e9;
const int sz = 1e5+1;
int n,m;
vector<int> last(sz);
vector<vector<int> > adj(sz);
vector<int> d(sz,0);
void solve()
{
cin>>n>>m;
for(int i=0; i<m; ++i)
{
int a,b;
cin>>a>>b;
adj[a].push_back(b);
}
queue<int> q;
q.push(1);
while(!q.empty())
{
int s = q.front();
q.pop();
for(auto u : adj[s])
{
if(d[s]+1>d[u])
{
d[u]=1+d[s];
last[u]=s;
q.push(u);
}
}
}
if(d[n]==0)
{
cout<<"IMPOSSIBLE"<<endl;
return;
}
vector<int> ans;
int k=n;
while(k!=1)
{
ans.push_back(k);
k=last[k];
}
ans.push_back(1);
reverse(ans.begin(), ans.end());
cout<<1+d[n]<<endl;
for(int i=0; i<ans.size(); ++i)
cout<<ans[i]<<" ";
cout<<endl;
}
int main()
{
solve();
}
So the solution is O(n+m) but still, there is TLE in one case. Why?
Name |
---|
tried to do the same, got TLE on the LAST Test Case. Solved the problem with topological sort. Link to code https://cses.fi/paste/95851f6ac3e4e45919f087/
Understood, thanks
I think test cases are weak in CSES for this problem.
AC on Date: 13/09/2022
using stack inplace of queue made it work