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 | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
CSES Longest Flight Route TLE in one test case
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?
| Rev. | Lang. | By | When | Δ | Comment | |
|---|---|---|---|---|---|---|
| en5 |
|
salt_n_ice | 2020-12-03 13:46:13 | 56 | ||
| en4 |
|
salt_n_ice | 2020-12-03 13:45:53 | 62 | Tiny change: 'Problem : ' -> '<spoiler summary="Spoiler">\n...\n..testing\n</spoiler>\nProblem : ' | |
| en3 |
|
salt_n_ice | 2020-12-03 13:41:51 | 16 | ||
| en2 |
|
salt_n_ice | 2020-12-03 13:40:55 | 73 | ||
| en1 |
|
salt_n_ice | 2020-12-03 13:39:52 | 1329 | Initial revision (published) |
| Name |
|---|


