Submission #839927

#TimeUsernameProblemLanguageResultExecution timeMemory
839927pere_gilLongest Trip (IOI23_longesttrip)C++17
5 / 100
1018 ms608 KiB
#include "longesttrip.h" #include "bits/stdc++.h" using namespace std; #define vi vector<int> #define ii pair<int,int> const int mxn=257; vector<int> adj[mxn]; ii dfs(int u, vector<bool> &vis, vi &res, bool sw){ vis[u]=true; ii best={0,u}; int nxt=u; for(int v: adj[u]){ if(vis[v]) continue; ii act=dfs(v,vis,res,sw); if(act.first+1>best.first) best={act.first+1,act.second},nxt=v; } if(sw && nxt!=u) res.push_back(nxt); return best; } vi longest_trip(int n, int d){ for(int i=0;i<mxn;i++) adj[i].clear(); for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(are_connected({i},{j})) adj[i].push_back(j),adj[j].push_back(i); vector<bool> first(n,false),second(n,false); vector<int> res; for(int i=0;i<n;i++){ if(first[i]) continue; vi act; int st=dfs(i,first,act,false).second; dfs(st,second,act,true); act.push_back(st); reverse(res.begin(),res.end()); if(act.size()>res.size()) res=act; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...