#ifndef Nhoksocqt1
#include "longesttrip.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 260;
#ifdef Nhoksocqt1
bitset<MAXN> adjp[MAXN], idA, idB, bsA, bsB;
struct Jury {
int n, d;
void init(int _n, int _d) {
n = _n, d = _d;
int u, v;
bool check(0);
while(cin >> u >> v) {
adjp[u][v] = adjp[v][u] = 1;
check = 1;
}
if(!check) {
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
int cnt = adjp[i][j] + adjp[i][k] + adjp[j][k];
if(cnt < d) {
vector<ii> p;
p.push_back(ii(i, j));
p.push_back(ii(i, k));
p.push_back(ii(j, k));
while(cnt < d) {
int r = Random(0, 2);
if(adjp[p[r].fi][p[r].se])
continue;
++cnt;
adjp[p[r].fi][p[r].se] = adjp[p[r].se][p[r].fi] = 1;
}
}
}
}
}
}
}
bool are_connected(vector<int> &A, vector<int> &B) {
bsA = bsB = idA = idB = 0;
for (int it = 0; it < sz(A); ++it) {
bsA |= adjp[A[it]];
idA[A[it]] = 1;
}
for (int it = 0; it < sz(B); ++it) {
bsB |= adjp[B[it]];
idB[B[it]] = 1;
}
return ((bsA & idB).count() > 0 || (bsB & idA).count() > 0);
}
} jury;
#endif // Nhoksocqt1
int numNode;
bool adj[MAXN][MAXN], dx[MAXN];
bool check_are_connected(vector<int> &A, vector<int> &B) {
#ifdef Nhoksocqt1
return jury.are_connected(A, B);
#else
return are_connected(A, B);
#endif // Nhoksocqt1
}
int dfs(int u, int len, vector<int> &ans) {
dx[u] = 1;
if(len == numNode) {
ans.push_back(u);
return true;
}
for (int v = 0; v < numNode; ++v) {
if(!dx[v] && adj[u][v]) {
if(dfs(v, len + 1, ans)) {
ans.push_back(u);
return true;
}
}
}
dx[u] = 0;
}
int evaluation(int u) {
vector<int> tmp;
while(1) {
dx[u] = 1;
tmp.push_back(u);
int maxLen(0), v(-1);
for (int i = 0; i < numNode; ++i) {
if(!dx[i] && adj[u][i]) {
v = i;
break;
}
}
if(v < 0)
break;
u = v;
}
int res = sz(tmp);
while(sz(tmp)) {
dx[tmp.back()] = 0;
tmp.pop_back();
}
return res;
}
int evaluation2(int u) {
vector<int> tmp;
while(1) {
dx[u] = 1;
tmp.push_back(u);
int maxLen(0), v(-1);
for (int i = 0; i < numNode; ++i) {
if(!dx[i] && adj[u][i]) {
int len = evaluation(i);
if(maxLen < len) {
maxLen = len;
v = i;
}
}
}
if(v < 0)
break;
u = v;
}
int res = sz(tmp);
while(sz(tmp)) {
dx[tmp.back()] = 0;
tmp.pop_back();
}
return res;
}
vector<int> longest_trip(int N, int D) {
numNode = N;
if(D == 3) {
vector<int> ans;
for (int i = 0; i < numNode; ++i)
ans.push_back(i);
return ans;
}
for (int u = 0; u < numNode; ++u) {
for (int v = u + 1; v < numNode; ++v) {
vector<int> A, B;
A.push_back(u);
B.push_back(v);
adj[u][v] = adj[v][u] = check_are_connected(A, B);
}
}
for (int i = 0; i < numNode; ++i)
dx[i] = 0;
vector<int> ans;
int len(0), u(-1);
for (int i = 0; i < numNode; ++i) {
int z = evaluation2(i);
if(len < z) {
len = z;
u = i;
}
}
while(1) {
dx[u] = 1;
ans.push_back(u);
int maxLen(0), v(-1);
for (int i = 0; i < numNode; ++i) {
if(!dx[i] && adj[u][i]) {
int len = evaluation2(i);
if(maxLen < len) {
maxLen = len;
v = i;
}
}
}
if(v < 0)
break;
u = v;
}
return ans;
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "longesttrip"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
int n, d;
cin >> n >> d;
jury.init(n, d);
vector<int> path = longest_trip(n, d);
cout << "ANSWER: " << sz(path) << ": ";
for (int it = 0; it < sz(path); ++it)
cout << path[it] << ' '; cout << '\n';
return 0;
}
#endif // Nhoksocqt1
Compilation message
longesttrip.cpp: In function 'int evaluation(int)':
longesttrip.cpp:117:13: warning: unused variable 'maxLen' [-Wunused-variable]
117 | int maxLen(0), v(-1);
| ^~~~~~
longesttrip.cpp: In function 'int dfs(int, int, std::vector<int>&)':
longesttrip.cpp:108:11: warning: control reaches end of non-void function [-Wreturn-type]
108 | dx[u] = 0;
| ~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Execution timed out |
3002 ms |
480 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
340 KB |
Output is correct |
| 2 |
Correct |
37 ms |
344 KB |
Output is correct |
| 3 |
Execution timed out |
3048 ms |
344 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Correct |
39 ms |
344 KB |
Output is correct |
| 3 |
Execution timed out |
3015 ms |
344 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Correct |
36 ms |
344 KB |
Output is correct |
| 3 |
Execution timed out |
3100 ms |
344 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
