Why i am getting TLE at this cses problem,need helppppppppppp

Revision en1, by mainnahihoo, 2025-09-28 18:52:36

this problem is minimal task Link can be solved by dp, i am using bfs or djikstra u can say , so i made a priority_queue and when first time when my string will be having the size of 2*n-1 means i had reached to end so this will be the answer lexicographically

see the code i am getting TLE no wrong answer i think worst complexity will be O(N^2) ,Please help


struct cmp { bool operator()(const pair<pair<int,int>,string> &x, const pair<pair<int,int>,string> &y) const { return x.second > y.second ; } }; int check(int i,int j,int n){ return i>=0 && j>=0 && i<n && j<n; } string ans; vector<pair<int,int>>dir={{1,0},{0,1}}; string bfs(int i,int j,vector<vector<char>>&vec,vector<vector<int>>&vis,int n){ priority_queue<pair<pair<int,int>,string>,vector<pair<pair<int,int>,string>>,cmp>pq; string s; s+=vec[i][j]; pq.push({{i,j},s}); while(!pq.empty()){ auto it=pq.top();pq.pop(); string temp=it.second; if(it.second.size()==(n*2 - 1)){ return it.second; } for(auto &i:dir){ int new_x=it.first.first+i.first; int new_y=it.first.second+i.second; if(check(new_x,new_y,n) && vis[new_x][new_y]==-1){ vis[new_x][new_y]=1; pq.push({{new_x,new_y},temp+vec[new_x][new_y]}); } } } } void solve() { // executing code from here int t=1; while (t--) { int n; cin >> n; vector<vector<char>> vec(n,vector<char>(n,'.')); vector<vector<int>> vis(n,vector<int>(n,-1)); for (int i = 0; i < n; i++){ for(int j=0;j<n;j++){ cin>>vec[i][j]; } } cout<<bfs(0,0,vec,vis,n)<<endl; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // sieve(); solve(); return 0; }

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English mainnahihoo 2025-09-28 18:52:36 2086 Initial revision (published)