이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
// Subtask 1: D == 3
vector<int> sub1(int n) {
vector<int> res(n);
std::iota(res.begin(), res.end(), 0);
return res;
}
// Subtask 2: D == 2
bool has_edge(int u, int v) {
return are_connected({u}, {v});
}
vector<int> sub2(int n) {
vector<int> res {0};
for (int i = 1; i < n; i++) {
if (has_edge(0, i)) {
res.push_back(i);
break;
}
}
for (int i = 1; i < n; i++) {
if (i == res[1]) continue;
if (has_edge(res.back(), i)) {
res.push_back(i);
} else {
res.insert(res.begin(), i);
}
}
return res;
}
// Subtask 3: D == 1, return path with length >= Lmax / 2
vector<int> sub3(int n) {
// maintain 2 paths
vector<int> p1 {0}, p2 {1};
for (int i = 2; i < n; ++i) {
// consider p1.back(), p2.back(), i
// -> there's at least 1 edge
if (has_edge(p1.back(), i)) {
p1.push_back(i);
} else if (has_edge(p2.back(), i)) {
p2.push_back(i);
} else {
reverse(p2.begin(), p2.end());
p1.insert(p1.end(), p2.begin(), p2.end());
p2 = {i};
}
}
if (p1.size() > p2.size()) return p1;
return p2;
}
// Subtask 4: D == 1
vector<int> sub4(int n) {
// Use subtask 3 to get 2 paths {{{
vector<int> p1 {0}, p2 {1};
for (int i = 2; i < n; ++i) {
if (has_edge(p1.back(), i)) {
p1.push_back(i);
} else if (has_edge(p2.back(), i)) {
p2.push_back(i);
} else {
reverse(p2.begin(), p2.end());
p1.insert(p1.end(), p2.begin(), p2.end());
p2 = {i};
}
}
// }}}
// Make p1 longer path
if (p1.size() < p2.size()) swap(p1, p2);
if (p2.empty()) return p1;
// Impossible to merge 2 paths
if (!are_connected(p1, p2)) {
return p1;
}
// Merge 2 paths:
// Consider: p1[0], p1.back() and p2[0] -> at least 1 edge
if (has_edge(p1.back(), p2[0])) {
p1.insert(p1.end(), p2.begin(), p2.end());
return p1;
} else if (has_edge(p1[0], p2[0])) {
reverse(p2.begin(), p2.end());
p2.insert(p2.end(), p1.begin(), p1.end());
return p2;
}
// p1 is now a circle
// corner case: |p2| == 1
if (p2.size() == 1) {
for (int i = 0; i < p1.size(); ++i) {
if (has_edge(p1[i], p2[0])) {
reverse(p2.begin(), p2.end());
p2.insert(p2.end(), p1.begin() + i, p1.end());
p2.insert(p2.end(), p1.begin(), p1.begin() + i);
return p2;
}
}
}
// Consider: p2[0], p2.back() and p1[0] -> at least 1 edge
if (has_edge(p2[0], p1[0])) {
reverse(p1.begin(), p1.end());
p1.insert(p1.end(), p2.begin(), p2.end());
return p1;
} else if (has_edge(p2.back(), p1[0])) {
p2.insert(p2.end(), p1.begin(), p1.end());
return p2;
}
// p2 is now also a circle
// Find one edge from p1 -> p2
int l1 = 0, r1 = p1.size() - 1; // p1[l1..r1] has at least one edge to p2
while (l1 < r1) {
int mid = (l1 + r1) / 2;
if (are_connected(vector<int> (p1.begin() + l1, p1.begin() + mid + 1), p2)) {
r1 = mid;
} else l1 = mid + 1;
}
for (int i = l1; i <= l1; i++) {
for (int j = 0; j < p2.size(); j++) {
if (has_edge(p1[i], p2[j])) {
vector<int> res;
res.insert(res.end(), p1.begin() + i + 1, p1.end());
res.insert(res.end(), p1.begin(), p1.begin() + i + 1);
res.insert(res.end(), p2.begin() + j, p2.end());
res.insert(res.end(), p2.begin(), p2.begin() + j);
return res;
}
}
}
return p1;
}
vector<int> longest_trip(int n, int d) {
if (d == 3) return sub1(n);
if (d == 2) return sub2(n);
return sub4(n);
}
컴파일 시 표준 에러 (stderr) 메시지
longesttrip.cpp: In function 'std::vector<int> sub4(int)':
longesttrip.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i = 0; i < p1.size(); ++i) {
| ~~^~~~~~~~~~~
longesttrip.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int j = 0; j < p2.size(); j++) {
| ~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |