| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 853972 | FairyWinx | 가장 긴 여행 (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
#ifdef LOCAL
vector<vector<int>> G_secret;
int n;
bool are_connected(vector<int> a, vector<int> b) {
for (int i : a) {
for (int j : b) {
if (G_secret[i][j])
return true;
}
}
return false;
}
#endif
struct dsu {
vector<int> p;
dsu(int n) {
p.resize(n);
iota(all(p), 0);
}
int get(int a) {
if (p[a] == a)
return a;
return p[a] = get(p[a]);
}
void merge(int a, int b) {
a = get(a), b = get(b);
p[a] = b;
}
};
vector<int> get_comp(int n, int v, dsu &d) {
vector<int> comp;
for (int i = 0; i < n; ++i) {
if (d.get(i) == v) {
comp.push_back(i);
}
}
return comp;
}
void add_comp(vector<int> &ans, vector<int> &comp, pair<int, int> end) {
ans.push_back(end.first);
for (int j : comp) {
if (j != end.first && j != end.second) {
ans.push_back(j);
}
}
if (end.first != end.second) {
ans.push_back(end.second);
}
}
vector<int> longest_trip(int n, int D) {
dsu d(n);
vector<vector<int>> path;
vector<pair<int, int>> ends;
ends.push_back({0, 0});
path.push_back({0});
vector<int> ost(n - 1);
iota(all(ost), 1);
while (true) {
int ind_comp = ost[0];
bool find = false;
bool was_merge = false;
for (int i = 0; i < (int) ost.size(); ++i) {
if (are_connected({ends.back().second}, get_comp(n, ost[i], d))) {
path.push_back(get_comp(n, ost[i], d));
int last_end = ends.back().second;
ends.emplace_back();
for (int i : path.back()) { // поиск вершины.
if (are_connected({last_end}, {i})) {
ends.back().first = i;
}
}
if (path.back().size() == 1) {
ends.back().second = ends.back().first;
} else {
if (ends.back().first != path.back()[0]) {
ends.back().second = path.back()[0];
} else {
ends.back().second = path.back().back();
}
}
swap(ost[i], ost.back());
ost.pop_back();
find = true;
break;
} else {
was_merge = true;
d.merge(ost[i], ind_comp);
swap(ost[i], ost.back());
ost.pop_back();
--i;
}
}
if (was_merge)
ost.push_back(ind_comp);
if (!ost.size()) {
vector<int> ans;
for (int i = 0; i < (int) path.size(); ++i) {
add_comp(ans, path[i], ends[i]);
}
// cout << "MEOW1\n";
return ans;
}
if (!find) {
vector<int> last_comp = get_comp(n, ost[0], d);
for (int i = 0; i < (int) path.size(); ++i) {
if (are_connected({last_comp[0]}, {ends[i].first})) {
vector<int> ans;
for (int j : last_comp) {
if (j != last_comp[0]) {
ans.push_back(j);
}
}
ans.push_back(last_comp[0]);
for (int j = i; j < (int) path.size(); ++j) {
add_comp(ans, path[j], ends[j]);
}
for (int j = 0; j < i; ++j) {
add_comp(ans, path[j], ends[j]);
}
// cout << "MEOW2\n";
return ans;
}
}
vector<int> ans;
for (int i = 0; i < n; ++i) {
if (i != last_comp[0]) {
ans.push_back(i);
}
}
// cout << "MEOW3\n";
return ans;
}
}
return {-1};
}
#ifdef LOCAL
int main() {
int n, m, d;
cin >> n >> m >> d;
G_secret.resize(n, vector<int> (n));
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
G_secret[a][b] = G_secret[b][a] = 1;
}
auto z = longest_trip(n, d);
cout << z.size() << '\n';
for (int i : z) {
cout << i << ' ';
}
cout << '\n';
for (int i = 0; i < (int) z.size() - 1; ++i) {
if (!G_secret[z[i]][z[i + 1]]) {
cout << "Хуйня, а не путь\n";
return 0;
}
}
}
#endif