#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;
cout << p[r].fi << ' ' << p[r].se << '\n';
}
}
}
}
}
}
}
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
vector<int> A[MAXN];
int nxt[MAXN], 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 evaluation(int u, int lenNow, int pNxt[]) {
int nxt[numNode + 1];
for (int i = 0; i <= numNode; ++i)
nxt[i] = pNxt[i];
vector<int> tmp;
while(1) {
dx[u] = 1;
tmp.push_back(u);
++lenNow;
int v(-1), prv(-1);
for (int i = nxt[numNode], j = numNode; i < numNode; j = i, i = nxt[i]) {
if(!dx[i] && adj[u][i]) {
v = i, prv = j;
break;
}
}
if(v < 0)
break;
nxt[prv] = nxt[v];
u = v;
}
while(sz(tmp)) {
dx[tmp.back()] = 0;
tmp.pop_back();
}
return lenNow;
}
int evaluation2(int u, int lenNow, int pNxt[], vector<int> &ans) {
int nxt[numNode + 1];
for (int i = 0; i <= numNode; ++i)
nxt[i] = pNxt[i];
vector<int> tmp;
while(1) {
dx[u] = 1;
tmp.push_back(u);
++lenNow;
int maxLen(0), v(-1), prv(-1);
for (int i = nxt[numNode], j = numNode; i < numNode; j = i, i = nxt[i]) {
if(!dx[i] && adj[u][i]) {
int len = evaluation(i, lenNow, nxt);
if(len == numNode) {
maxLen = len;
v = i, prv = j;
}
}
}
if(v < 0)
break;
nxt[prv] = nxt[v];
u = v;
}
ans = tmp;
while(sz(tmp)) {
dx[tmp.back()] = 0;
tmp.pop_back();
}
return lenNow;
}
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);
}
}
nxt[numNode] = 0;
for (int i = 0; i < numNode; ++i) {
dx[i] = 0;
nxt[i] = i + 1;
}
vector<int> ans;
int u(0);
while(1) {
dx[u] = 1;
ans.push_back(u);
int maxLen(0), v(-1), prv(-1);
for (int i = nxt[numNode], j = numNode; i < numNode; j = i, i = nxt[i]) {
if(!dx[i] && adj[u][i]) {
int len = evaluation(i, sz(ans), nxt);
if(len == numNode) {
maxLen = len;
v = i, prv = j;
}
}
}
if(v < 0)
break;
nxt[prv] = nxt[v];
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 evaluation2(int, int, int*, std::vector<int>&)':
longesttrip.cpp:139:13: warning: variable 'maxLen' set but not used [-Wunused-but-set-variable]
139 | int maxLen(0), v(-1), prv(-1);
| ^~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:197:13: warning: variable 'maxLen' set but not used [-Wunused-but-set-variable]
197 | int maxLen(0), v(-1), prv(-1);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Correct |
18 ms |
344 KB |
Output is correct |
| 3 |
Correct |
141 ms |
344 KB |
Output is correct |
| 4 |
Correct |
373 ms |
340 KB |
Output is correct |
| 5 |
Correct |
873 ms |
492 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Correct |
24 ms |
344 KB |
Output is correct |
| 3 |
Correct |
137 ms |
344 KB |
Output is correct |
| 4 |
Correct |
413 ms |
344 KB |
Output is correct |
| 5 |
Correct |
945 ms |
720 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Correct |
25 ms |
344 KB |
Output is correct |
| 3 |
Partially correct |
121 ms |
344 KB |
Output is partially correct |
| 4 |
Partially correct |
413 ms |
344 KB |
Output is partially correct |
| 5 |
Partially correct |
896 ms |
492 KB |
Output is partially correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 7 |
Halted |
0 ms |
0 KB |
- |
