Submission #979991

#TimeUsernameProblemLanguageResultExecution timeMemory
979991vjudge1Longest Trip (IOI23_longesttrip)C++17
0 / 100
3074 ms2416 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector <int>; using vll = vector <ll>; const ll MAXN = 256; vll adj[MAXN]; ll mat[MAXN][MAXN]; // diameter common fishel L pair <ll, vi> bfs (ll n, ll u) { vector <char> vis(n, false); vll dis(n), from(n); queue <ll> q; vis[u] = true; dis[u] = 0; from[u] = u; q.push(u); ll far = u; while (q.size()) { ll u = q.front(); q.pop(); for (ll v : adj[u]) { if (vis[v]) continue; vis[v] = true; dis[v] = dis[u]+1; from[v] = u; q.push(v); far = v; } } ll ffar = far; vi path; while (far != from[far]) { path.push_back(far); far = from[far]; } path.push_back(far); return { ffar, path }; } vi longest_trip (int n, int d) { fill(adj, adj+n, vll({})); for (ll u = 0; u < n; u++) { for (ll v = u+1; v < n; v++) { if (are_connected(vi({ int(u) }), vi({ int(v) }))) { adj[u].push_back(v); adj[v].push_back(u); mat[u][v] = true; mat[v][u] = true; } else { mat[u][v] = false; mat[v][u] = false; } } } vi ans = {}; for (ll v = 0; v < n; v++) { vi pans = {}; for (ll u = 0; u < n; u++) { vi path = bfs(n, bfs(n, 0).first).second; if (path.size() > pans.size()) pans = path; } deque <int> dq(pans.begin(), pans.end()); ll ex1 = dq.front(), ex2 = dq.back(); vector <char> vis(n, false); for (ll u : dq) vis[u] = true; for (ll u = 0; u < n; u++) { if (vis[u]) continue; if (mat[u][ex1]) { dq.push_front(u); ex1 = u; } else if (mat[u][ex2]) { dq.push_back(u); ex2 = u; } } pans = vi(dq.begin(), dq.end()); if (pans.size() > ans.size()) ans = pans; } return ans; }
#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...