This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |