#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
vector<int> A[MAXN];
int tr[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
}
class DisjointSet {
private:
vector<int> lab;
public:
DisjointSet(int _n = 0) {
lab.assign(_n + 7, -1);
}
int find(int u) {
return (lab[u] < 0) ? u : (lab[u] = find(lab[u]));
}
bool join(int u, int v) {
u = find(u), v = find(v);
if(u == v)
return (false);
if(lab[u] > lab[v])
swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return (true);
}
} dsu;
ii dfsFar(int u, int p) {
ii res = {1, u};
for (int it = 0; it < sz(A[u]); ++it) {
int v(A[u][it]);
if(v != p) {
ii tmp = dfsFar(v, u);
tr[v] = u;
++tmp.fi;
res = max(res, tmp);
}
}
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;
}
vector<ii> edge;
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);
if(adj[u][v])
edge.push_back(ii(u, v));
}
}
vector<int> ans;
while(1) {
for (int i = 0; i < numNode; ++i)
A[i].clear();
dsu = DisjointSet(numNode);
shuffle(edge.begin(), edge.end(), rng);
for (int it = 0; it < sz(edge); ++it) {
int u(edge[it].fi), v(edge[it].se);
if(dsu.join(u, v)) {
A[u].push_back(v);
A[v].push_back(u);
}
}
int x = dfsFar(0, -1).se;
ii res = dfsFar(x, -1);
if(res.fi >= (numNode + 1) / 2) {
int y(res.se);
while(y != x) {
ans.push_back(y);
y = tr[y];
}
ans.push_back(x);
break;
}
}
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
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Execution timed out |
3072 ms |
1760 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
344 KB |
Incorrect |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
344 KB |
Output is correct |
2 |
Correct |
23 ms |
344 KB |
Output is correct |
3 |
Correct |
150 ms |
728 KB |
Output is correct |
4 |
Execution timed out |
3025 ms |
1524 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
344 KB |
Incorrect |
3 |
Halted |
0 ms |
0 KB |
- |