이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define INF 2000000002
#define MAXN 1000000
int n, m, nxt[MAXN + 3];
bool visited[MAXN + 3];
vector<pair<int, int> > points;
vector<int> cycleLengths;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int w, e;
cin >> w >> e;
points.push_back({w, e});
points.push_back({e, w});
}
memset(nxt, -1, sizeof(nxt));
sort(points.begin(), points.end());
for (int i = 0; i < points.size(); i++) {
auto [x, otherEnd] = points[i];
int idx = upper_bound(points.begin(), points.end(), make_pair(otherEnd, INF)) - points.begin();
nxt[i] = idx;
}
memset(visited, false, sizeof(visited));
// Process the line graph
int numNodesInLineGraph = 0;
int currentNode = 0;
while (currentNode != -1) {
numNodesInLineGraph += 1;
visited[currentNode] = true;
currentNode = nxt[currentNode];
}
// Process the cycles
for (int i = 0; i < 2 * n + 1; i++) {
if (!visited[i]) {
int currentNode = i;
int cycleLength = 0;
while (!visited[currentNode]) {
cycleLength += 1;
visited[currentNode] = true;
currentNode = nxt[currentNode];
}
cycleLengths.push_back(cycleLength);
}
}
sort(cycleLengths.begin(), cycleLengths.end(), greater<int>());
// Connect the line graph with the cycles while possible
for (int i = 0; i < cycleLengths.size() && m > 0; i++, m--) {
numNodesInLineGraph += cycleLengths[i] + 2;
}
// If we can add more teleports..
numNodesInLineGraph += (m/2) * 4 + (m%2);
cout << numNodesInLineGraph - 1 << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
teleporters.cpp: In function 'int main()':
teleporters.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i = 0; i < points.size(); i++) {
| ~~^~~~~~~~~~~~~~~
teleporters.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i < cycleLengths.size() && m > 0; i++, m--) {
| ~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |
# | 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... |
# | 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... |
# | 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... |