| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 960593 | TAhmed33 | 가장 긴 여행 (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
bool adj2[256][256];
int cnt;
bool are_connected (vector <int> x, vector <int> y) {
bool flag = 0;
for (int i = 0; i < (int)x.size(); i++) {
for (int j = 0; j < (int)y.size(); j++) {
flag |= adj2[x[i]][y[j]];
}
}
return flag;
}
vector <int> tree[256];
bool vis[256];
vector <int> x;
int p[256];
set <int> unvis;
void dfs (int pos) {
vis[pos] = 1; x.push_back(pos); unvis.erase(pos);
while (true) {
vector <int> t; for (auto i : unvis) t.push_back(i);
int l = 0, r = (int)t.size() - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
vector <int> g;
for (int i = 0; i <= mid; i++) g.push_back(t[i]);
cnt++; assert(cnt <= 3000);
if (are_connected({pos}, g)) {
r = mid - 1; ans = mid;
} else {
l = mid + 1;
}
}
if (ans == -1) break;
tree[pos].push_back(t[ans]);
p[t[ans]] = pos;
dfs(t[ans]);
}
}
int get (int x) {
if (tree[x].empty()) return x;
return get(tree[x][0]);
}
vector <int> longest_trip (int n, int d) {
cnt = 0;
unvis.clear(); for (int i = 0; i < n; i++) unvis.insert(i);
for (int i = 0; i < n; i++) tree[i].clear();
memset(p, -1, sizeof(p));
memset(vis, 0, sizeof(vis));
x.clear(); dfs(0);
if (!unvis.empty()) {
vector <int> ret = x;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
x.clear(); dfs(i);
if ((int)x.size() > (int)ret.size()) ret = x;
}
}
return ret;
}
int pos = -1;
for (int i = 0; i < n; i++) {
if ((int)tree[i].size() == 2) {
pos = i;
}
}
if (pos == -1) return x;
int u = get(tree[pos][0]), v = get(tree[pos][1]);
if (p[pos] != -1 && !are_connected({p[pos]}, {u})) {
swap(u, v); swap(tree[pos][0], tree[pos][1]);
}
u = tree[pos][0], v = tree[pos][1];
while (!x.empty() && x.back() != p[pos]) x.pop_back();
vector <int> l;
while (true) {
l.push_back(u);
if (tree[u].empty()) break;
u = tree[u][0];
}
reverse(l.begin(), l.end());
for (auto i : l) x.push_back(i);
x.push_back(pos);
while (true) {
x.push_back(v);
if (tree[v].empty()) break;
v = tree[v][0];
}
return x;
}
mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());
int random (int l, int r) {
return uniform_int_distribution <int> (l, r) (rng);
}
int main () {
/* int n; cin >> n;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
int x; cin >> x;
adj2[i][j] = adj2[j][i] = x;
}
}
auto z = longest_trip(n, 1);
for (auto i : z) cout << i << " ";
cout << '\n';
return 0;*/
while (true) {
vector <int> x, y;
int n = random(1, 5);
for (int i = 0; i < n; i++) {
if (random(1, 2) == 1) x.push_back(i);
else y.push_back(i);
}
memset(adj2, 0, sizeof(adj2));
for (int i = 0; i < (int)x.size(); i++) {
for (int j = i + 1; j < (int)x.size(); j++) {
adj2[x[i]][x[j]] = adj2[x[j]][x[i]] = 1;
}
}
for (int i = 0; i < (int)y.size(); i++) {
for (int j = i + 1; j < (int)y.size(); j++) {
adj2[y[i]][y[j]] = adj2[y[j]][y[i]] = 1;
}
}
vector <pair <int, int>> dd;
bool flag = 0;
for (int i = 0; i < (int)x.size(); i++) {
for (int j = 0; j < (int)y.size(); j++) {
if (random(1, 2) == 1) {
adj2[x[i]][y[j]] = adj2[y[j]][x[i]] = 1;
flag = 1;
}
}
}
auto z = longest_trip(n, 1);
if (flag) {
if ((int)z.size() != n) {
cout << n << '\n';
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
cout << adj2[i][j] << " ";
}
cout << '\n';
}
return 0;
}
} else {
if ((int)z.size() != max((int)x.size(), (int)y.size())) {
cout << n << '\n';
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
cout << adj2[i][j] << " ";
}
cout << '\n';
}
return 0;
}
}
}
}